I'm not being paid by these people, but I've started online lessons via Skype and Skype text chat with an outfit in Nanjing (at least my particular teacher seems to be in Nanjing) and I'm very pleased with the result thus far. If you're in Taiwan you might be able to get the same thing via a language school, but for those of us who are not, this is the greatest thing since sliced bread so far IMHO.
I'm paying US$6.25 an hour (12 classes for US$75; you can get 1 for $7 and a free 20-minute intro lesson; payment through PayPal). At those prices, I'm seriously considering indulging myself with four a week when I get organized. The teacher I've got is open-minded (!) with my choice of "learning materials" (I'm doing sight translations of English speeches into Chinese with her just now, although I want to branch out into directed discussions on specific branches of industry to enrich my vocab). I don't have any special equipment on my computer, not even a microphone or speakers (it's a laptop) either. I also like the Chat feature as we write our notes on what's going on that way, and it's admittedly far easier for me to write using a computer than by hand
but as I'm not terribly concerned about that failure on my part, this way is more efficient for her or me to write the new words and for me to make notes on their usage in a way that's automatically saved by the program. I don't know if there's a whiteboard on SkypeChat or not; that would probably be useful for anyone who was just learning to write characters. Probably there is, or you could use a videoconferencing hookup.
There are probably other services out there that do the same thing, but this is one of the least expensive I've found, and it's rare to find teachers who can take on advanced-level students with confidence. This might be more common in the Mainland...? since the general belief there seems to be "Of course foreigners can learn Chinese", as opposed to the doubt and incredulity that are daily fare in Taiwan. "Millie" does a wonderful job and I'm looking forward to bothering her with many hours of my awkward sight translations.
URL is http://www.chinesetutor.net/index.html