Уж точно стоит искать не на русских сайтах, как, например ВКонтакте или Одноклассники, потому что там крайне мало иностранцев в принципе. Можно использовать Facebook.com и искать там случайных людей, но есть и специальные сайты, на которых можно найти носителя нужного языка и пообщаться с ним, а человек сам в этом заранее заинтересован, например:
Отличный сайт, на котором можно найти товарища по переписке из любой страны мира. Дичайше советую. Сортировать предполагаемых собеседников можно по полу/возрасту/стране/языкам.
Есть сайт interpals.net. При регистрации там указывается ваш уровень знания языков, а также какие вы хотели бы изучить/подтянуть. Так что помимо возможности найти носителей различных языков, можно и на своём пообщаться с иностранцами, которые изучают ваш родной, либо которым вы хорошо владеете.
Можете попробовать поискать на специализированных форумах, благо таких предостаточно, просто забейте в поисковике и лучше на английском языке.
Мне, кстати, тоже очень интересен данный вопрос, так как есть знакомые знакомых интересные в коммерческом плане. Надо их найти и пообщаться, а как это сделать я не знаю тоже.
В AppStore есть приложение - Tandem. Люди по всему миру общаются на разных языках, включая английский. После запуска приложения вы можете сразу позвонить американцу.
Добавлю к уже перечисленным ресурсам Italki.com. Кстати очень странно, что его никто не указал, на мой взгляд это самый удобный сайт языкового обмена. Хотя даже там найти адекватных иностранцев заинтересованных в русском языке (реально заинтересованных и готовых учиться, а не тех, кто просто в профиле его указал как изучаемый) довольно трудно.