Is it possible to find a good job only with fluent English (also Ukrainian, Russian)?
Yes... but not so easy... you have to try hard... may find a very good job or nothing... Try some companies trading with FSU...
Is it a big problem for my future employer to give me job offer if I have only Shengen Visa with no permission to work?
I don't know but If they will really need you then they will probably take care about the papers...
5. Medical insurance - is it expensive in Poland and how can I buy insurance for myself at least for 6 months?
If you are legally employed then the insurence is paid by the employer...