My question is, is it possible to enroll without masters degree into PhD in Germany? I know that in US, UK Masters degree is not a pre-requisite for PhD. How about in Germany?
Yes, in Germany, as well as many (most?) other places in central Europe, a Masters degree is a formal requirement for starting a PhD.
The reason for this is mostly historical - in Europe, we did not really have Bachelor and Master degrees until 2000 or shortly thereafter. Essentially, before ~2000, a "Diploma" (sort of equivalent to master's degree, a bit of a mixture of MSc and MBA) was the first degree you could get from an university. Around 2000, the so-called Bologna process went into action, with the goal of homogenizing the way how higher eduction works across Europe, and the chosen target model was the traditional Bachelor / Master / PhD model of US universities. Of course, adopting this model in the somewhat different realities of european universities meant that what was really implemented in many places was sort of a half-hearted mixture of old and new system. For instance, in my country of origin (Austria), almost every study basically just took the their old "Diplomstudium" (old curriculum, where the equivalent of MSc was the first degree) and more or less randomly awarded a BSc after 3 years. Of course, at this point, the student did not have a completed education in any way - the curriculum was fully designed that students do another 2 years after master studies afterwards (and the majority of students does so). As a result, public opinion, for instance in industry, of people with "only" a bachelor are not very good -- in many ways, those are considered people who stopped their studies prematurely. In a similar vain, universities also require a "completed" undergrad study (which, in Austria, means doing the entire 5-year original master studies) before being allowed to enroll into a PhD programme.
Now, that being said, I find it more than just a bit awkward that your department in Germany did not clarify this in advance. This issue is not an unknown quantity in Germany -- everybody who hires even occasionally from outside of Europe should know about this and handle this issue in advance. I am afraid it will be a difficult problem to solve.
Can't my research experience be accounted as qualification ?
I highly doubt it. This is not just a small administrative hurdle -- in many places (I do not know about Germany, though), the requirement of a Master to get enrolled to a PhD programme is defined by national university law, so it is not a requirement that a university or professor can just waive for you.