Entries in Early References
J.S. Farmer & W.E. Henley, Slang and Its Analogues (1890–1902) reports a number of oaths associated (facetiously) with Moses. First it offers this entry:
BY THE EVER-LIVING JUMPING MOSES! inf[initive] phr[ase] An effective ejaculation and moral waste-pipe for interior passion or wrath is seen in the exclamation. BY THE EVER-LIVING JUMPING MOSES!—a harmless phrase, that for ["from" in Hotten] its length expends a considerable quantity of fiery anger.—Hotten [A Dictionary of Modern Slang, Cant, and Vulgar Words, second edition (1860)].
Then it offers these two entries in the H section—the only two that are exclamations:
HOLY JUMPING MOTHER OF MOSES. See MOSES.
HOLY MOSES. See Moses.
Under MOSES, we get these additions:
BY THE PIPER THAT PLAYED BEFORE MOSES, phr[ase] (common).—An oath. Also BY THE HOLY JUMPING MOTHER OF MOSES. See OATHS.
Unfortunately there is no entry for OATHS in Farmer & Henley. But the book does provide some relevant early quotations:
1855 STRANG, Glasgow and Its Clubs, 243. But HOLY MOSES! what a rear?
1876 HINDLEY, Adventures of a Cheap Jack, p. 109 Screw your courage to the sticking place and BY THE HOLY-JUMPING-MOTHER-OF-MOSES—who was my uncle—we'll not fail.
1890 HUME NISBET, Bail Up! 212. 'And, BY THE PIPER THAT PLAYED BEFORE MOSES, so they did,' replied her companion coolly.
I should perhaps provide some context for the Strang quote from 1855. Strang is describing the "martial spirit" prevailing in Glasgow following the peace of Amiens of 1803 and the obesity of some members of the city's volunteer Armed Association:
Although this redoubtable body, like all other sons of Mars of that warlike period, wore a uniform—and a uniform, too, for which each was indebted to his own tailor,—still it must be allowed that, from the great variety of lank and paunchy forms which it enveloped, it by no means made a uniform body of men. Hence the wonder will not appear great, when it is mentioned, that on dressing the line of the "Armed Association," the drill sergeant, himself a noted Irish marine crimp and wag, should have exclaimed on one occasion,"Very well, the front rank; but holy Moses! what a rear!"
The phrase "holy Moses" was not originally a facetious or euphemistic expression, however, but a standard epithet for Moses, as is clear from this quotation under the Farmer & Henley entry for "TO STAND MOSES":
1611 COTGRAVE, Dictionarie ... HOLIE MOYSES, whose ordinarie counterfeit having on either side of the head an eminence, or lustre, arising somewhat in the forme of a horne, hath imboldened a prophane author to stile cuckolds parents de Moyse.
Entries in Later References
Eric Partridge, A Dictionary of Slang and Unconventional English, Fifth Edition (1961) supplements the list of "holy" epithets in Farmer & Henley with several others from the nineteenth century, including these:
holy kicker!; holy smoke. Exclamations expressive of amazement: late C 19–20.
holy show!; h. lance! A mild oath: ca. 1850–1910: the latter not gen.
J. E. Lighter, The Random House Dictionary of American Slang (1994) makes a fairly strong case for the notion that the "holy " part of "holy Moses" was less crucial to the exclamation (or mild oath) than the pairing of some vivid adjective or phrase with Moses. Lighter presents citations for the following variants (with dates):
"The suffering Moses!" (1869, by Mark Twain in Innocents Abroad); "Thunder 'n' Moses!" (1877); "Mighty Moses!" (1881); "Whistling Moses!" (1919); "Great bull-rushin' Moses!" (1920); "Thunderin' Moses" (1920); "Bellowin' Moses!" (1928); "Moses on the mountaintop!" (1932); "Hey, the holy sneakun Moses!" (1932).
The use of holy as an adjective attached to a nonreligious noun may have gained considerable steam in the 1940s, thanks to Captain Marvel. Here is Lighter's entry for moley:
moley n. [pop. as a characteristic exclamation of "Captain Marvel," hero of a series of comic books begun in 1940 ... perh. reflecting moly 'magic herb in Greek mythology', in allusion to the invocation of mythological figures as a source of the character's powers; perh. euphem. and rhyming alt. of holy Moses] In phrase: holy moley (used as an expression of surprise).
It's really not much of a leap from Captain Marvel saying "Holy Moley! He got away!" in 1949 to Robin saying, "Holy Guacamole, Batman!" on the 1966–1968 TV series Batman.
Robert Chapman & Barbara Kipfer, Dictionary of American Slang, Third Edition (1995) provides a useful summary of first occurrence dates for various forms of "holy NOUN" exclamations:
holy cats interj (Variations: cow or gee or mackerel or Moses or schmutz or shit or smoke or sox may replace cats) entry form [holy cats] by 1900, cow by 1940s, gee by 1895, mackerel by 1903, Moses by 1900, schmutz by 1990s, shit by 1940s, smoke by 1889, sox by 1909 An exclamation of surprise, wonder, dismay, admiration, etc. ... [euphemisms for holy Christ]
Chapman & Kipfer takes the view that all "holy NOUN" exclamations began as euphemisms for "holy Christ." It appears from the extreme difference in arrival dates of, for example, "holy show," "holy kicker," "holy smoke," "holy lance," and "holy cats" (some as early as the 1850s, and all by 1910) and "holy shit" (by 1940s) that the palliative euphemisms came much earlier than the exacerbating ones—although the more offensive a term is deemed to be, the longer it may exist underground before appearing in mainstream publications.
This progression seems reasonable to me—and if it is accurate, it points to the conclusion that, in all exclamations of the "holy FILTHY EXPLETIVE" type, the "holy" came before the "FILTHY EXPLETIVE" as part of a word-pair interjection. Of course, filthy expletives have been around for a long time themselves, as solo performers; so, from another point of view, trying to figure out which came first—"holy" + later expletive, or expletive + later "holy"—may not make much sense.
In searching for early instances of the term "holy shit" in Google Books, I came across a scholarly volume that the OP and other interested parties may find worth reading: Melissa Mohr, Holy Shit: A Brief History of Swearing (Oxford University Press, 2013). The online excerpt from the book consists of Mohr's introduction and the book's opening chapter (on swearing/obscene oaths in Rome), which will give you a sense of Mohr's approach; Colin Burrow posts an interesting review of the whole book in the London Review of Books under the heading "Frog's Knickers," in which he also recommends a book by Geoffrey Hughes titled Swearing: A Social History of Foul Language, Oaths and Profanity in English (1991).