The only thing I could really say is, practice. Out loud, if possible. With variations.
Like: "hi, my name is...", "My name's... What's yours", "I'm... You?"
If you can get comfortable talking to yourself, or rehearsing to yourself, it may make it easier.
I don't have to practice introducing myself for general circumstances anymore, but if I'm trying to talk with a woman I have a crush on I do a lot of it. And I do quite a bit of scripting, sometimes, and will often rehearse parts of that out loud. You may even try doing it in front of a mirror, or a video camera.
I got kind of lucky with introductions. My first job was as a caddy, so I had to learn how to introduce myself, shake hands, respond to variations of "how are you doing?" appropriately.
My second job was stocking coolers at a ridiculously busy convenience store, started at about 15. So I watched lots and lots of people.
I have a weird problem with difficulty pronouncing my own name, Andrew, if I'm applying it to myself, but not if it's someone else's.