A few years ago, I found some exchange requests on the skype forum - with international people looking for help with their english whilst offering help with spanish (where spanish was their native language).
Of course, it still takes a bit of effort - but it proved to be a wonderful resource that in other circumstances, had every right to be expensive rather than free! You will find many spanish (or south american) people who's english is actually excellent - but they just need to practice conversation. That then makes it easier for them to help you with some basic spanish.
I gave up eventually (time constraints). However, the time spent was enjoyable and the bits I did learn have still come in useful whenever I visit Spain.