A website I have used is: de.worldsbiggestchat.com (or chat.lycos.de). It's the biggest German chat I've ever found. You might give that a try.

You can also try at www.babbel.com It is a website for learning other languages and you meet there like here people from all over the world. But other than here you have a chat for the different languages: English, French, Spanish.... and of course, German. In all chats you meet native speakers. The advantage of such a chat is that the people know that you come into because you learn that language and they help you.

In Germany. Or try the chat here. Otherwise search on Skype, Yahoo, MSN, etc.

I usually chat with Germans on Facebook. Some uses twitter, too.

Ich brauche einen deutschen Partner