There are certainly major challenges in trying to research in Russia and states that were part of the Soviet Union.
Have you looked at the Ukrainian Archives?
There are apparently no online sources for genealogy, but the archive will apparently contract for research. I personally have no experience with this. See this link for more details: https://archives.gov.ua/Eng/genealogia.php
There is also a link for Jewish research on this website. See: http://www.rtrfoundation.org/index.shtml
A website I use for research in areas of the former Austro-Hungarian Empire, which includes Galicia and parts of the Ukraine, www.genteam.at, does not have much on the Ukraine.
The website Matricula Online has a very limited amount of Polish records, but I expect there will be more in the future. See http://data.matricula-online.eu/en/
I have no experience with Polish Archives, but a google search should yield information on the Archives.
FamilySearch has some Ukrainian records (various churches, including some Jewish records). Go to the catalog and search Ukraine and you will get a list of quite a number of resources. You could also search for the town you are interested. I did notice that some of the catalog entires are in either Ukrainian or Russian (I will admit I cannot tell the difference - but I do know there are a few differences in the Ukrainian and Russian alphabets).
Best of luck.