A mio parere, un blocco dinamico PL/SQL è alquanto oscuro. Sebbene sia molto flessibile, è anche difficile da mettere a punto, da eseguire il debug e da capire cosa succede. Il mio voto va alla tua prima opzione,
EXECUTE IMMEDIATE v_query_str INTO v_num_of_employees USING p_job;
Entrambi usano le variabili di binding, ma prima, per me, è più modificabile e sintonizzabile dell'opzione @jonearles.