Just diving into random conversation in any language until you know a great deal of vocabulary is never easy or a great idea. If you consider that the average native speaker of any language knows upwards of 20'000 words, how can you possible hope to just have a random conversation of any kind until you yourself know thousands of words. 

It is much beter, I feel, and from my experience to be much more focused with language exchange. Agree in advance one or two topics that you will discuss the next time you met, and stick as much as possible to those topics. This way you can prepare for your conversation, look up and learn words that you would expect to maybe come up. For example if you are going to discuss music you might want to look up names of instruments, types of music, words relating to tempo, feelings etc etc. Try prparing a list of questions to ask your partner related to that topic and try to tell them in your own words what they have just told you.

Keep the conversation short. It is much better to have a 10 minute chat about one subject and really get something out of it, rather than try and talk for half an hour and getting frustrated and not learning much. 

It's probably the way you organise exchanges. I believe that lower levels should focus on the basics, not try to make complicated conversations.

It's better to practice what you know and gradually add new vocabulary and grammar.

I think the key point when progressing at Chinese is controlling your expectations.

As an exampes, I had studied Italian, which took me 3 months to get to conversational level,  French, which took me 2 months to be able to have reasonable conversations, Chinese: took my 3 years before I was confident enough to have actual, non-classroom conversations with people, and I still sounded like a moron!

I'm not saying here that's it's going to take you three years to get anywhere, but Chinese simply isn't a language you're going to just pick up quickly. It's a little bit like muscle building: you just have to put in the hours, and focus on short-term goals. All Chinese learners are in the same boat, there's nothing wrong with you, I promise!

you just described what I feel about my Russian! ;(

I can see by your profile that you are a good cantonese speaker, so why are you lack of confidence for learning Mandarin, they are all chinese languages. you can learn it well just like cantonese