Hi Anuka,
I definitely have experience with this in other contexts, but I've been able to overcome it for the most part. So, I hope that I can offer some helpful advice.
I do find it strange that you have this problem in Martial Arts, though. For me, getting together and training with fellow martial artists is one of the most comfortable social contexts I engage in on a regular basis, because we all share a common interest. I have a deep personal interest in martial arts, and I enjoy being able to discuss it with other people who equally interested. It takes the focus off of you as an individual, and allows you to both discuss something external. Moreover, most instructors and even fellow classmates are very receptive to anyone who expresses a genuine interest in the art. Don't be afraid to ask questions or discuss your observations -- as long as you're humble about it, people will almost always welcome the discussion.
So, for me at least, it's easiest to connect with people by focusing on a shared goal or interest, and talking about that. I think that's generally the case - so don't be shy in this regard. You don't even need to worry about yourself or the other person, just discuss that interest which you share.
More importantly though, and I think this is the most important advice I can give you:
Accept yourself for who you are. Know who you are, and embrace that.
There's nothing wrong with being introverted, or even shy.
There's nothing wrong with not enjoying, or not being able to make small talk, even.
You don't have to socially outgoing if that's not who you are. Thinking that way will only make you feel inadequate, and more awkward. But, that's a mistake. The truth is, you're simply judging yourself by the wrong standards. Einstein had a great saying: "Everybody is a genius. But if you judge a fish by its ability to climb a tree, it will live its whole life believing that it's stupid."
Like you, I'm terrible at small talk. And, I'd be surprised if you could find anyone more introverted than I am. Yet, I really enjoy getting out, training, and even socializing (at least, for as long as my social battery holds out) with other martial artists. And more and more, I'm coming to enjoy interacting with people in other contexts as well. This is mainly because I just shifted my focus: I stopped being concerned so much with other's standards and how they might be thinking of me, and I started focusing more on my own standards and values, and just being myself, whoever that person is. I find that I'm actually very personable when I do this, because I allow myself to be authentic, and be relaxed about it. When I'm not worried about being something - "interesting," or "entertaining," or "outgoing," I can be what I actually am: thoughtful, curious, open-minded, and unassuming. And as a result, I enjoy myself more, and people enjoy being around me more.
For me, I just aim to be personable and approachable. I'll occasionally comment on things that I'm left thinking about, or am curious of, and that often leads to very interesting discussions. I just share my thoughts when I feel like doing so, and don't worry about it (or try to come up with something to say) when I don't. If you're putting any pressure on yourself at all trying to find something to say or contribute to a conversation, you're hindering your actual ability to do so.
As a last piece of advice, you may want to really get to know yourself and how you think, as well as a better understanding of how others think. People's personalities, aptitudes, and approach to life vary greatly, and it can be helpful to know how you fit into that picture. I've found Myers-Briggs / Jungian Functions to be very helpful in this role. If you look into typing yourself accurately (by actually digging into, and exploring the psychological functions, and not just taking one of the many silly tests that are out there - though, feel free to start with one just for fun, as long as you take the results with a shaker full of salt

), you may find that it really forces you to become honest with yourself and start differentiating between who you tell yourself you are, and who you really are -- digging underneath the layer of assumptions that you may hold, or things that you may have attributed to yourself which may or may not accurately reflect who you are. It may sound funny, but a lot of people don't have a very accurate perception of themselves. Really digging down and discovering who you are is an important step to actually accepting yourself for who you are, and being comfortable being that person.
Anyway, I know I got rather long-winded and rambly, but hope at least some of that was helpful!