To speak fluently, most of all you need to love talking that on it's own would help you to build confidence. There is a difference beetwen fluent and correct. Being understood by others it is vital in every day to day living but what you will find most people don't have a patient to speak grammatically correctly not to mention all different accents.
You need to be good listener, that way you will get better understanding form a conversation rather that trying translate word by word. Talking is like a book we read a book and we know what the story was about, but if I ask what have you read on specific page it would be impossible for you to know.
My point is that instead interrupting every minute listen for longer, from my experience not only I got better at talking I also gain a respect as most people like people who listen. That way you are borrowing their words in reply -for example to their question.