Łukasz, first of all, I am pretty sure you can use your Polish Visa/Mastercard card in Ukraine and withdrawal issues would most likely be related to your bank which issued the card, and not the Ukrainian network of ATM and bank offices. Make sure to visit your local bank prior to going to Ukraine and make sure they unlock your card for operations abroad.
Ukrainian banks do provide accounts to non-residents. My guess would be that this scenario is not so typical and you might need to be prepared to explain what you need and maybe even insist it's possible :) If bank staff do not know or are unsure what to do with a non-resident, they might prefer to tell you that they cannot do it. You won't be the client they fight for or even someone they feel a need to please.
It took me a bit of time to find a proof link about personal accounts for non-residents but here you go: Pravex Bank writes [in Russian, sorry] that a non-resident needs a passport to open an account. There is similar information here from Bank Forum:
Non-residents of Ukraine (including citizens of Ukraine, permanently
residing abroad, foreign citizens and stateless persons, staying in
the territory of Ukraine on the basis of applicable visa or documents,
confirming legitimacy of their stay in Ukraine according to applicable
legislation) shall require the following documents:
- statement, confirming the sources of funds in Hryvnias and foreign currency
If you speak Ukrainian or Russian, I would suggest emailing a bank in advance with a question about documents you need to open a current/card account as a non-resident. A printed reply from the bank would be helpful when you visit an office here. To give you some lead here, you can ask Lviv's Idea Bank this question and their email is here.
Make sure to keep all receipts with you that explain money transfers, deposits, withdrawal and currency exchange operations. By law non-residents are basically limited in what they can do, e.g. they can buy foreign currency only for the money they have proof of origin for. If you throw receipts away, you won't be able to sell hryvnias when you don't need them anymore (or, you will have to ask some resident to do the foreign exchange operation, which might be not so difficult). I would not be surprised if you will have to even declare currency (even though you don't need to declare an amount under NNN) when you enter Ukraine to have a document explaining where you obtained the money from when you deposit it into your account.
All in all, I would say that you can both use your Polish card and open an account here, and the biggest obstacle on this way is going to be to explain what you need and have paperwork available with you.