I've been to Ukraine, although only Kiev and Chernobyl (and the train from and to Rzezow, Poland).
My Russian at the time was very limited. But for me the most important step was learning to read Cyrillic. Just being able to sound out letters suddenly makes train stations, street signs and the like manageable.
I still don't speak Russian - aside from a few words. However, I've been to Ukraine, Russia twice, and several of the stans (eg Uzbekistan) where Russian was spoken very commonly. It's still very possible to get around, even in the small towns.
Firstly, I picked up a few key phrases. "Where is....". "Hello". "Goodbye". "Please". "Thank you". "Do you have....?". "Bus station". "Train station". "How much". "I don't speak Russian".
Just a few like that are surprisingly useful. Also some numbers.
But as an example, say I'm in village X and want to get to village Y. I'd go up to the shared taxi pool (or bus station or whatever) and ask for 'bus na Y'. They'd say something I couldn't understand in Russia, so I'd say 'I don't speak good Russian'. 'How much?'. They'd either whip out their phone and write the number on the screen, or write it in the dust on the car window. I'd then cross it out and write a new number (negotiating price without words!). When we agreed, I'd hop in and off we'd go.
For train stations, I used to find this really hard, but now have it sorted. Before going up I'd write in Cyrillic the name of the station I wanted to go to. This was easy as the names are all up on the departure wall anyway. Then I'd write the date, time, and the class I wanted to go - 'Kupe', for example. Then I'd draw two bunks, with an arrow to the top one (I want the top bunk). I'd show that to the attendant, and ask how much. Easy enough, worked almost every time (once the train wasn't running, that was a tough conversation).
Ordering food? To ask if it was pork or chicken once, I pointed at the words and made the two sounds - a sort of 'oink' and 'squawk'. The waiters thought it was hilarious, but when he brought out my food, he pointed at the kebabs and made the noises himself to identify them. Made everyone smile, and again, conversation was possible without language.
My point of these examples is mostly, everyone is friendly, and happy to meet people from far away (there will be exceptions). And with waving of arms, some careful thought about writing or drawing, and a select phrase list, I was able to get around and see and do almost everything I wanted, without a guide or tour group.
Yes it'll be frustrating at times, there may be delays, but as long as you're happy to accept it as part of the experience, it's all good fun :)