и так, и так.
Зачастую это делается одновременно, но обязательного правила нет.
здесь вопрос не в том, что должно пройти время, должно быть ясное подтверждению данному факту (что нет претендентов в германии на позицию).
если компания уже год ищет и не может найти и ищет в том числе через ведомство по труду - разрешение могут дасть сразу, в противном случае - могут и заставить подождать два месяца.
и причина здесь проста - ведомство по делам иностранцев должно быть уверено в том, что специалиста нет в германии. для этого оно запрашивает ведомство по труду проверить данный факт. если компания уже обращалась туда неоднократно... ну понятно.
касательно вопроса - пусть подает работодатель, ну и вы тоже сразу же после подавайте (вам это нужно, чтобы формально срок соблюсти, если будут тянуть). То есть может быть ситуация - работодатель получил добро, а консульство из принципа тянет (у меня так было в первый раз).
если вы подадите раньше работодателя на месяц - то вам могут гипотетически формально отказать в консульстве - так как время истекло, а разрешение не получено.
так что подавайте одновременно. пусть немецкая фирма делает вам предложение сейчас (возможно с оговоркой - оно действительно при получении разрешения на работу, в получении которого они содействуют). никаких страховок не делайте - после получения разрешения сделаете.