Other than はじめまして, what else can we say at the beginning of our introduction when meeting someone for the first time? Also, what else do we need to say when introducing ourselves other than our name that will be considered polite by the Japanese people? Can someone give me an example in Japanese of a good way of introducing ourselves for the first time?
はじめまして is a good start. This is how you open the conversation. It's roughly equivalent to "How do you do?" (which people don't really say anymore). You're indicating that it's your first meeting, so you are extending a courteous greeting.
Usually, the next step is to say your name: (In my case) ロバートと申します (very polite) ロバートと言います/です (a little more casual). Sometimes you can give details about yourself before your name to give the other person a better idea of who you are. オーストラリアから来たロバートです. (I'm Robert; I come from Australia). Alternatively, you could say whose friend you are, what you're studying or at what level, or what section of the company you work in.
At this point, your partner will introduce themselves.
Now you indicate you hope you can get along in future (roughly the same as "nice to meet you" in English), and add a bow.
To be more polite (for instance in business situations) you can say いたします instead of します.
Your partner will return this greeting.
Depending on the situation, you can have more small talk to clarify who the other person is or identify yourself more clearly.
There can be more casual ways of doing this. You could say よろしく instead of よろしくお願いします, for instance.
If you're non-Japanese, typically the other person wants to know where you are from, how and for long you have studied Japanese, when you came to Japan, what you're doing in Japan and so on. There will usually be a customary compliment on your Japanese level, which you are supposed to downplay with まだまだです (I'm not quite good at it yet) or some equivalent.
If you make a mistake in your introduction, Japanese people are generally forgiving, in my experience.
(That is usually how it goes from my 1.5 years of living in Japan.)
Though the answer might depend on the purpose you came to Japan, after making the simple self-introduction such as Robert showed, I recommend you to say not by yourself but by the interpreter what you noticed at the entrance, what you were interested in on the street, what made you in trouble on the way to here, the place where you want to visit tonight, etc. except what you knew in preconceptions before coming to Japan. The newer is the better, and the more unpredictable is the better.
Probably there will be various reactions for your additional self-introduction like simple answers, advice, proposals, invitations, etc. from the Japanese who heard it.
I thereby think you may achieve the purpose that you came to Japan for more smoothly, earlier and more efficiently, thanks to the additional self-introduction.