Podle mého názoru je dynamický PL/SQL blok poněkud obskurní. I když je velmi flexibilní, je také těžké ho vyladit, těžko ladit a těžko zjistit, co se děje. Můj hlas patří vaší první možnosti,
EXECUTE IMMEDIATE v_query_str INTO v_num_of_employees USING p_job;
Obě používají proměnné vazby, ale za prvé, pro mě, je více znovu detelovatelné a laditelné než možnost @jonearles.