Skype is your best solution here, I think.
Also check out Language Learning with Livemocha | Learn a Language Online - Free!
In hindsight, I think that site helped me more than any other to learn the Cyrillic alphabet, even though it doesn't explain Cyrillic at all! I learnt a few words simply by ear, and then along with seeing them written down, began to understand the connection between the written symbols and the sounds. It was only when I came across something that I couldn't understand (for instance, why was "молодой" pronounced "muh-lah-DOY" instead of "mo-lo-DOY"?) that I referred to other sites.
Using this "learning by example" method, I actually found learning Cyrillic to be very easy, I think it took me less than a week. (And I hardly even use livemocha any more.)