aquamarine and Haruto are right: i tried it twice, some years ago but it never worked because both of us were forced to use a foreign language (english), and our skills were not good enough to let us chit chat about everything, so we had to keep our emails on general arguments.
quite boring and time consuming, but what is worse is that it didn't lead to anything, even if we were armed with the best intentions.
(edit: just to clarify, "it didn't lead to anything" means that we wanted to learn each other language but we couldn't)
a simple google search will bring you everything you will ever need, and i'm linking a nice site just as example:
http://www.japan-guide.com/penfriend/
i don't know if it's good or not, but sure it's free (it requires registration though)