I am agree with you.To make a language partner is very hard .It depends on their location(time difference) ,purpose,enthusiasm and get along well.Its a miracles.but If you express your purpose in detail.Every one find you more easily.

If you don't know what to talk about, look at the news in the paper and discuss an article that you both find interesting. I could be the latest elections, immigration, art, climate change,...whatever,  just do this in a language learning context and soon you will get more comfortable.

Mine usually proceed with 'How long have you been studying/practicing [language]", "Do you want to have voice calls in [language]?", then first call (or text) is age,studies/job, family, living accomodations, hobbies, after that: http://iteslj.org/questions/

I have been studying languages online for many years and what I fine has worked out best are topics like:

-- Tell me about your city/town.

-- Describe your work/school.

-- How do celebrate the holidays? What are your traditions?

And of course, -- What is your weather like?

I tend to avoid current events and politics. Besides being controversial (espeically across countries), the langauge needed to really discuss these tends to be more advance.

If you'd like, send me a message with one such topic and I will correct/suggest and answer. :-)

Good luck!

There are so many phrases which you can use while getting the attention of someone. for instance: 

Hey, I'd like to negotiate with you, If you like too, let me know.

Hi, I love to be your language partner, If you agree, send me friend request. thanks.

Hello, How're you doing today. I've read your profile and I wish to be your language partner. and I think, we'd be proven good language partners.

You can proceed your conversation with a number of phrases, depending on the person you wish to take up with. 

...

wish you good luck. @Maria