There is an important difference between Polish and German flat rent market. In Poland you often find landlords accepting the first tenant they get, without doing any background check nor demanding any deposit (in German: “Kaution”). In Germany on the other hand (or in most Western countries), it is normal that you have to provide a secure and stable source of income, or at least have some other people (usually your parents) that are financally secure to pledge, that they are going to pay instead of you, should the need arise.
It is indeed difficult to find a flat in this crazy circle: You can't get a work permit because you have no flat, and you can't rent a flat because you don't have a job. I've been there myself.
I got over this with the help of my parents. They had to fax their pay record from last 3 months and sign a declaration, that they are going to cover my expenses. It works fine, you may have to shop arround though. Not every landlord will be fine with accepting something like this.
But don't sweat! There is another, cheaper way! There is a site called https://www.couchsurfing.org/ where you can find people willing to accomodate you for some time. I wouldn't count on a longer stay than 1, maybe 2 weeks but hey! It's free! This maybe just long enough to find yourself a flat and do all the work you need to get things going. The other good thing about couchsurfing is, your host can be a valuable source of information. He can show you the city and maybe even help in looking for a flat. Afterwards you are not completely alone in the city. You have somebody to hang out with.
If you are alone in a City and need on the ground support it won't hurt to ask lokal priests for help. They are usually nice people, most of the younger ones know english and could help you with filling out complicated forms in german.