I think it you were going to do this on a bigger scale you'd need to have specific lesson plans and conversation topics as well as tips for both the native and learning speakers. For example, tell learner how to ask how to properly phrase a sentence.
Another idea is to have the people on both ends learning each other's language, so rather than teacher-student, both are students, one learning Spanish and the other learning English, for example.
The conversations are awkward.
Cambly and Verbling are interesting startups.
I've studied a lot of languages.
Arbitrary conjugation logic prevents any sort of resourcefulness once you've exhausted cognates and repetitive conjugations.
http://kumar.vc/2013/01/27/language-learning-is-broken/
I believe the solution to language learning rests somewhere in providing a viable way to learn arbitrary conjugation logic at an aggressive speed.
For learning French I started with Duolingo and once I got where I knew 100 words or so started going to FIAF to watch French movies and plays and eventually interacting with native speakers, both tourists and expats. Since we were all there for the same event there was a natural starting point for the conversation. This also has the advantage that there are people around that know enough English and French to give an assist in the case where we hit a limit to my/their knowledge of the other's language.
There are a few more I would like to learn and suspect that a similar approach is going to be effective.
It would be interested if... You could "earn" credits by teaching someone your language, which could be redeemed to learn a language from someone else. It is a workable business model where you basically get teachers for "free" and a certain portion of the users pay into it to get credits.
In places like here in China there is a huge demand for 'language partners'. Mostly Chinese looking for English-speaking people, but a lot of foreigners trying to learn Chinese. And many cases where both want to learn from each other.