Opening an account in German bank is possible to do remotely, e.g. via regular mail or online. Some of them do open accounts for foreigners living outside Germany. Unfortunately, in many cases, the list of supported countries does not include Romania.
However, if you search carefully, there are also banks that can open accounts remotely for foreigners living outside Germany including Romania, e.g. DKB, comdirekt, Consorsbank (for these 3 banks I just checked if it is possible to put Romania for both citizenship and place of residence in the application form of these banks) etc. All these accounts are free of charge, e.g. there is no monthly fee.
Another option could be that you go to bank in Germany in person and ask them to open an account for you.
Besides that, I'm not sure why your employer asks you to provide them a valid German bank account. I doubt that this is a legal requirement, especially taking into account the fact that SEPA money transfers within an EU are free of charge.
Next, as far as I know, there is no law that requires you to have a bank account or credit score or even European citizenship or German visa to rent an apartment. Of course, it could be more complicated without it, but there are still may be some apartments available for rent, especially from private people. In some cities, under such a conditions, it can be extremely hard to find an apartment, but there should be special options like dormitory for students, flats provided by your employer, apartments with furniture for short- and middle-term rent (example for Potsdam: https://how8.de/en/), AirBnB (if it is allowed in the city and if you can get a proper rental agreement for a couple of months), etc.
I'm also not sure if a rental agreement / registration is legally required for EU citizens to work in Germany. Imagine, if you fly every day to work or live in another country near Germany (e.g., Poland), you may live in that other country but work in Germany.
IMHO, if you move to Germany, the best way to start with legal issues is to rent an apartment and register there. Opening the bank account would be the next step.
P.S. I'm not a lawyer.