Ah yeah, I understand the language awful-ness. I do modern (really postmodern) Eastern Europe, specifically Czechoslovakia and I'm starting to do Romania. When I met with my advisor he said, "So, you're learning Romanian this summer." Yep, no idea where that money is coming from but apparently, I'm learning Romanian this summer!
Russian is not the easiest language to learn but there are some great summer institutes for it - Middlebury in Vermont is one of the best, as is SWSEEL at Indiana University. With both of those I believe you can get a year's worth of Russian done in six-nine weeks.
The problem with languages and working in a region you don't know the language is the limits in research. Foreign policy is definitely one you're probably going to need Russian for. And not just what we historians call "knowing a language" which is just for reading. That being said, UK degrees are only 1 year long (most are 1 calendar year as opposed to one academic year) so it's entirely possible that you could write your thesis without knowledge of Russian.
Do you want to stay in the UK/Ireland for a job or move back to the US? If you want to go back to the US I would highly advise sticking with only the three you mentioned. Newcastle, for example, has some great researchers on Eastern Europe but nobody in the US is going to recognize Newcastle.
I don't know about the programs themselves, but yes, UCL is incredibly expensive. I read an article the other day that said it's actually cheaper to live in Barcelona and commute from Barcelona to London than to live in London.
I wish you luck!