En mi opinión, un bloque PL/SQL dinámico es algo oscuro. Si bien es muy flexible, también es difícil de ajustar, difícil de depurar y difícil de averiguar qué pasa. Mi voto va para su primera opción,
EXECUTE IMMEDIATE v_query_str INTO v_num_of_employees USING p_job;
Ambos usan variables de vinculación, pero primero, para mí, es más modificable y ajustable que la opción @jonearles.