I did a quick Google search today to see what I could come up with for getting native-speaker tutors via video chat, and eduFire.com appears to really nail it, provided you have a few bucks to shell out. Tutors on eduFire explain what they can tutor in and set their own price in the profiles, and you just drop by, pick your tutor, arrange a time to meet with them via Skype video chat or whatever other method works for the two of you, and you're learning. The prices are all over the place, ranging from $10/hour for one native-English tutor I saw to $70/hour for one law-school graduate tutor (as a fellow law school grad, I'm glad to hear it).
The one recommendation I'd have for them is to set up a language exchange service, whereby you can teach your language to someone and they would teach their language to you, all free of any payments. It appears that in any case this can happen unofficially, but it'd be nice if they could make it an outright part of the package.
Update: After I put up the initial post, I noted an ad for Myngle on my blog. I clicked through to find what appears to be a direct competitor of eduFire. Sooner or later I'll have to do a side-by-side comparison of the two, but for now if any of you have done so I'd love to hear about your experiences.