기본적으로 노동허가는 누구에게나 가능합니다(난민,망명자를 빼구요)

가장 중요한것은 고용주의 업무처리 능력과 독일 내에서의 입지입니다.

고용하는 회사가 독일내에서 경제활동을 하여 독일경제에 기여하는바가 크고(이미 독일인을 많이 고용하거나 독일회사들과 교역이 많은회사이며, 상대적으로 유령회사나 실적이 없는회사는 어렵겠죠!)
그 회사에서 한국어를 모국어로 하는 노동자 혹은 특별한 자격을 가진자를 고용함에 있어서 개척자님이 적격자라고 판단하여 강력히 추천되어져야합니다.

왜냐하면 그 일자리를 대신 할 사람이 주위에 널려있다면 실업율이 높은 이때에 굳이 외국인에게 노동허가를 내어주지 않겠지요!

정리하자면 위의 조건을 충족시키는 고용주의 추천서를 바탕으로 노동청과 외국인청 그리고 담당업무의 성격 혹은 회사가 속한 상인 연합에서 허가를 받아야 합니다.

회사내 고문변호사가 있다면 쉬울 것이고 없다면 그 방면으로 경험있는 변호사를 통하는것이 빠르게 일이 진행될것입니다.

좋은 결과를 바라며.... 

사족: 배우자의 노동허가 유무와는 관계없습니다.

제 소견으로는 가능합니다. 저희도 비슷한 경우에서 받았거든요.
그러나 중요한 것은 그 일이 Selbststaendig냐 아니면 Fest냐 입니다. 만약 Fest이면 쉽게 받으실 수 있습니다. 그래도 아마 6주 이상 걸릴 겁니다. 빨리 신처하세요. 참고로, Selbstataendig란 자영업처럼 자기가 알아서 세금, 보험 내야 하는 것이고, Fest는 월급 자체에 세금, 보험이 이미 지불된 상태로 나옵니다. 제일 확실한 방법은 비자전문 변호사에게 일을 맡기는 겁니다.

상사 직원의 배우자로 체류허가가 나와 있다면 원칙상 독일에서 일을 할 수 없습니다.
아르바이츠암트의 허락을 받은 후에만 일을 할 수 있습니다.
이 허락 또한  변호사를 통해서 받아보려고 하다보면 받을 수 있거나, 운이 좋은 경우가 생겨서 받는 것입니다. 신청인의 능력에 따른 것이지요.
독일에 살면서 원칙이 뭔지는 알고 살았으면 합니다.

답변이 아니어서 죄송합니다.
저도 비슷한 문제가 생겨서 문의 드립니다.

저는 독일에서 공부를 마쳤고, 공부를 마친 후 개인적인 사정으로 일을 할 상황이 아니어서, 학업 종료 후 주는 체류기간을 1년 채우기 전에 동반비자로 변경을 하였습니다. 동반비자에는 박사과정에 있는 배우자의 학업이 끝남과 동시에 효력을 상실한다고 적혀 있습니다. 당시 동반비자로 변경할 때, 혹시 나중에 취업을 하게 될 경우, 동반비자일 때 노동허가를 받는 것이 어렵지 않은 지에 대해 문의 했는데, 담당 공무원은 별 문제 될 것이 없다면서 취업 했을 경우 체류허가 변경에 필요한 양식까지 줬습니다. 지금 현재는 학업을 마친 후 1년 이상의 시간이 경과 했습니다.

최근 상황이 바뀌어서, 독일에 주재하는 한국회사에 지원을 했고 취업이 되었습니다.
Arbeitserlaubnis를 신청하기 위해 외국인관청에 문의를 했는데, 제 현재 체류허가가 배우자의 학업 여하에 묶여 있기 때문에 노동허가를 받는 것이 어려울 것이라며, 공부를 끝내고 바로 신청을 했더라면 얘기가 달라졌을 거라 말합니다. 그래서 여기에서 학업을 마친 것이 노동허가를 받는데 참고가 되는 것이 아니냐고 물어보니, 그것과는 상관없이 현재 체류허가 상태만이 고려된다는 비논리적인 답변만 들었습니다. 게다가 신청서 제출 시, 회사에서 -노동허가 받는데 유리하도록- 추천서에 상응하는 서류를 첨부했는데, 그것은 받지도 않고, 일단 제가 일을 할 수 있는 지 심사가 끝난 다음에 만약 일을 할 수 있는 자격이 되면 그 때 그 서류를 제출하라고 합니다. 여기 글을 읽어보면, 추천서가 있어야 노동허가를 받을 때 유리한 것이라고 알고 있는데 말입니다 (현재 서류는 제출한 상태입니다).

주 독일대사관 홈페이지에서 제공하는 생활법률 안내서에 나온 "입국및 체류에 관한 양해각서"를 보면, 2005년부터 - 배우자 유학 시- 동반비자를 소지한 사람도 취업이 가능한 것으로 되어 있습니다.:
----------------------------------------------------------------------------------------------
V. 양측은 유학목적으로 적법하게 상대국의 영역에 체류 중인 양국 국민들의 가족구성원들이 상대국의 영역에서 적용되는 관련법의 틀 안에서 비자영 피고용을 의도하는 경우에도 동반체류허가를 받을 수 있도록 하는 양측의 의지를 선언한다.

V. Beide Seiten bekunden ihren Willen, Familienangehörigen derjenigen Staatsangehörigen beider Seiten, die sich zum Zwecke des Studiums berechtigt im Hoheitsgebiet der jeweils anderen Seite aufhalten, zu ermöglichen, einen Aufenthaltstitel zum Familennachzug auch dann erhalten zu können, wenn diese dort im Rahmen des im Hoheitsgebiet der anderen Seite insoweit geltenden Rechts eine unselbständige Erwerbstätigkeit aufnehmen wollen.
----------------------------------------------------------------------------------------------

제가 알고 싶은 것은:
혹시 저와 같은 경우를 당하시거나, 주변에서 보신 적이 있으신지...
그렇다면 어떻게 해결을 하셨는지...
또 이런 경우를 전문으로 다루는 비자전문 변호사를 소개 받고 싶습니다.

미리 감사드립니다.

요즈음에는 함부르크. 프랑크푸르트등에 아르바이트 허가서를 1년 줬다가, 2년차에는 연장해 주지않는 경우도 보았습니다.
아마도 앞으로 더욱 어려워 질 것 같습니다.
독일에란 곳이 워낙 케이스 바이 케이스라서요...