First of all, it's important to understand how the word entered English. Despite some discussion to the contrary, it's clear that the word entered German from Yiddish, and not the other way around. It became popularized in German via the 1814 story "Peter Schlemihls wundersame Geschichte" ("Peter Schlemihl's Remarkable Story") by Adelbert von Chamisso. However, English apparently adopted the word shlemiel directly from Yiddish, not via German. (It is still used in German, and even the name of the Sesame Street muppet Lefty is "Schlemihl" in the German version).
Now to the Yiddish origins. I'll admit from the outset that I don't know the "true" origin, and I doubt any of us ever will. But I will review the various theories and tell you which seem more or less likely to me.
1) Even-Shoshan suggests that it is a corruption of the similar Yiddish word shlimazel (or schlimazel). Schlemazel is a combination of the German schlim (= "bad, crooked", related to the English "slim" ) and the Hebrew mazal מזל (= "luck").
However, the two words seem to be distinct, and are often paired together, as in the famous saying, "The shlemiel pours soup on the shlimazel" (and in the opening song of "Laverne and Shirley".)
2) Klein (in his entry for the Hebrew equivalent shelumiel שלומיאל) writes that it is "probably a transposition of shelo mo'il שלא מועיל (= useless)."
But a number of objections have been raised to this theory. I found two on the "Mendele: Yiddish literature and language" list archives. One is that while the phrase shelo mo'il is found fairly frequently in Talmudic Hebrew (and later), it "is suited for situations, acts, attempts at correction -- but not people." Another writer points out that
we would expect shelo mo'il to give something like *shloyml or *shlemoyl (the asterisk is used to indicate a form that does not exist). Since that is NOT what we find in Yiddish, the etymology in question cannot be accepted.3) The most popular explanation is that shlemiel comes from the Biblical Shelumiel ben Tzurishadai שלומיאל בן צורישדי - the prince of the tribe of Shimon (Bamidbar 1:6, 2:12, 7:36, 10:19). How did he become associated with the classic unfortunate bungler? There are a number of theories here as well:
a) One theory is based on the Talmud's claim (Sanhedrin 82b) that Shelumiel was one of the five names of Zimri, the prince of Shimon killed by Pinchas for sinning with a Midianite princess. Ignoring the fact that Shelumiel and Zimri lived a generation apart, Zimri doesn't seem "unfortunate" but "bad"! Why should the nickname come from him?
Rabbi Norman Lamm wrote an essay in 1974, called "The First Schelmihl". He claims that the shlemiel is not "hapless, luckless, a constant victim of conspiring circumstances", but rather is "sinister", "egotistical", and "will let no one and nothing stand in his way". While Lamm's homelitcal message is very powerful, it's hard for me to believe that the average person would make that jump, and understand that a real shlemiel is so evil. It just doesn't fit with the the way the word is used.
On the other hand, there are those that say that Zimri was unlucky, because while many were involved with the Midianites, he was the only one to get caught. But as Lamm pointed out, Zimri was clearly of a higher standing than the average person, and as the Talmud itself mentions, Zimri's act was as much of a rebellion against Moses as it was submission to passion.
Another question can be asked: if Zimri, for whatever reason, was the archetypal shlemiel, then why aren't we calling people zimris instead? One suggestion is that this was a private joke of the rabbis, to avoid recalling the improper nature of Zimri's act. Here too, I have difficulty accepting the idea that this kind of "conspiracy" would stick well enough to enter the popular jargon. In any case, the Talmud always refers to the culprit as Zimri, not Shelumiel, even such folksy sayings as "Their deeds are like those of Zimri, yet they ask for reward like Pinchas", so it doesn't seem likely that Zimri is our shlemiel.
b) A different theory suggests a connection between the unsuccessful fate of the tribe of Shimon (they were one of the smallest, didn't succeed in conquering their land) and "shlemiel". But again - it's a nice theory, but why use the name Shelumiel? (Rosten says in The Joys of Yiddish that Shelumiel was a general of Shimon who lost his battles, but then corrects himself in Hooray for Yiddish, choosing to follow the Zimri connection instead.)
c) Perhaps the most plausible Shelumiel theory that I've heard (first from my teacher Mitch Heifetz z"l) is mentioned here:
One suggestion relates to the arcane permutations of the Hebrew calendar. On Hanukkah a different section of Numbers 7 is recited daily, recounting the gifts of the tribal chieftains who each brought a daily offering at the dedication of the Tabernacle (mishkan). On the first day of Hanukkah, the first chieftain’s name appears at the beginning, on the second day the second chieftain’s name, and so on. (On the eighth day, the gifts of chieftains 8-12 are read.)While this does seem somewhat complicated, I can see how an average person might have noticed the fifth night's bad luck year after year (for a more positive take, see this Treppenwitz post.) However, Werner Weinberg (who taught us how to spell Chanukah here) writes in his Die Reste des Jüdischdeutschen that the first mention of this theory is in Halozebichel (Joke Book) of Rabbi Meir Ohnesorg, Prague 1864, p. 62. I couldn't find that book anywhere, but it seems possible that the whole etymology was just a joke.
The exception is the Sabbath during Hanukkah, when the Torah portion is that of the regular weekly cycle and the added maftir reading from a second scroll is the Hanukkah reading beginning with the daily chieftain. Only one day of Hanukkah’s eight never falls on a Sabbath: the fifth day. And which chieftain therefore never stars on the Sabbath, when the synagogue is far better attended than on a midwinter weekday morning? Why, Shelumiel ben Tsurishaddai, of course. Who else?
d) The last Shelumiel connection isn't a real theory at all, but still is important to mention. Heinrich Heine in his poem "Jehuda ben Halevy" writes that he heard the following "version" of the story from his friend Julius Eduard Hitzig (who, incidentally, was also friends with Chamisso):
But a legend amongst the people
Has been orally transmitted
Which denies that it was Zimri
Whom the spear of Phinehas slew.
And maintains that, blind with passion,
Phineas slew the transgressor,
but another who was guiltless --
Slew Schlemihl ben Zuri Schadday
This is clearly not what the Torah is describing, nor does it appear in any midrash. But it seems to have a lot of influence, and perhaps the very association of Shelumiel and shlemiel began with Heine (or Hitzig).
4) The last theory is presented by Leopold Löw (the father of Immanuel, who I've quoted often) in his book Die Lebensalter in der jüdischen Literatur (page 54). But instead of relating to a somewhat obscure biblical character, he find someone much closer to the age of Yiddish. In the responsa of the Maharil (1365 – 1427), he finds mention of a Rabbi named Shlomil (or perhaps Shlomel, likely a nickname for Shlomo or Shalom) of Enns, Austria, who had an unusual story:
וכן העיד שמה"ר שלומיל מעיר ענש הלך פעם אחת ללמוד למרחקים, ויהי לתקופת י"א חדשים ליציאתו ילדה אשתו והכל מעידין מרוב חסידותה ברור שלא זינתה תחתיו.
"And so testified Rabbi Shlomil of the city of Enns, that he once traveled far to study, and eleven months after he left his wife gave birth. But all know, that due to her righteousness, she clearly did not cheat on him [but rather had an unusually long pregnancy as mentioned in the Talmud, Yevamot 80b]"
Now while the Maharil clearly did not bring this story to make fun of Rabbi Shlomil (he quotes the same rabbi as his teacher in a number of other cases), but it is very possible that others did not view him with the same level of respect. Perhaps he was the classic case of someone who was in "the wrong place, at the wrong time"...