Dear Arnord.
It is indeed difficult finding a place to stay, especially in Berlin. But there are institutions that can help you find a room. Since you told me, that you are already having the Schein from Lageso that certifies that your room will be payed by the LeGeSo, you can contact the "Wohnungen für Flüchtlinge"
https://***.ejf.de/fluechtlingshilfe/fluechtlingsberatung/fluechtlingsberatung-berlin.html?MP=1765-2043
They are placed in Turmstr. 21, Haus K 10559 Berlin Moabit
They will help you personally to find a room and they even have a certain amount of apartments that they can give away directly to refugees.
In case you are looking for a shared flat. You can aswell contact "Flüchtlinge Willkommen" who can help you find a room, too.
Good luck
Best Henriette