Just moved to Berlin, no degree.
The federal employment agency had to give approval after the contract was signed, which took about 2-3 weeks. Working visa issued after 3 days.
HR shouldn't be scared, it's easy and pretty straightforward.
The general advice seems to be that a university degree is almost always required. Having another data point would be helpful!