EDIT: Cleaned up some bad wording, I was in a hurry earlier.
Is there any other way I can introduce myself?
Introduce your name with a sentence that is short and simple, and where it is clear which of the words is your name. "Hello! My name is XXXXX." Say the sentence in a normal voice; if you tend to speak quickly, then try your best to slow down just a little bit. Don't overdo it. Make sure that there is a pause immediately after your name. Not a long heavy pause, just a little bit of time to let it sink in.
Avoid something like "Hello, I'm xxx and I work at yyy". If you speak that one quickly, it will just go over their head.
Should I just spell my name out every time before someone even asks so that I don't have to repeat myself?
Definitely not!
Is it possible that this is more of a self-esteem issue than a spelling issue? Did you have problems with your name in school, have you been bullied because of it?
Spelling out your name (especially without being asked about it by the other party) would just lower yourself, and make it awkward for everybody.
It is really the job of the other person to "get" your name, to spell and pronounce it correctly. Some people don't care about things like this - just accept that. It's neither good nor bad, it just is. You are not your name, your name has no magic powers over you.
Other people may be fascinated and ask you about your name; this is perfectly normal as well. In this case, talk about your name; tell them what it means in your native language, tell a little story, and at the end maybe spell it out for them. Don't bore them, have a few small facts ready.
As a comparison: my own name is Germanic (old nordic German), and written in an unusual fashion. If I meet people, I tell them may name and they usually "get it". They never guess the spelling though, because it cannot be deduced from the sound. So I deliver the spelling immediately when somebody (a clerk maybe) is about to write/type my name.
In casual settings, I tell people two ways to abbreviate it (for example when they need to yell something at me during sports). This way, they know that I am fine with the abbreviation. There is also a well known movie in my country which has a main character of the same name; if I am in a really comfortable group I give a few funny quotes from that movie, making sure to let everyone know that I am very easy about all of this. In no-nonsense high-brow but yet relaxed situations, I am able to tell people what the name means, as well as link it to literature from 900 A.D. . :)
This approach (which obviously does not apply to you, directly) takes all kind of tension or awkwardness straight out, and I find people still use my full name just fine. My own story is of course not applicable to business life, but maybe you find some inspiration.