Here is the entry for all get-out in Harold Wentworth, American Dialect Dictionary (1944):
all get-out. 1. To an extreme degree; —used with like or as.
1884 We got to dig in like all git-out. Twain. 1909 Stubborn as all get-out, he was. Lincoln Cy Whit Place 13. [Other citations omitted.] 2. Euphem[ism] for hell, &c. 1939 Who in all git-out said so? Radio. 1939 Fl[orid]a[:] I sure as all get-out didn't figure [so].
The Twain quotation is from Huckleberry Finn (1884). Here is the dialogue where it appears:
"Geewhillikins," I says, "but what does the rest of it [Tom Sawyer's description of a coat of arms] mean?"
"We ain't got no time to bother over that," he says; "we got to dig in like all git-out."
"Well, anyway," I says, "what's some of it? What's a fess?"
The earliest instances of the phrase in a Google Books search use the forms "as all git out" and "like all git out." From Alexander Stimson, Easy Nat: Or, The Three Apprentices (1854):
'Ye're the cutest little hop-o'-my-thumb I ever saw,' said the farmer, wiping the tears from his eyes, 'but I must be goin'. I'm as hungry as all git out!' In a twinkling Scratch Gravel was by his side, and ready to accompany him. ' I'll show you the best hotel, Mister ; where all the country merchants go,' said he.
From Thomas Halliburton, The Americans at Home; or, Byeways, Backwoods, and Prairies (1855):
You'd better believe I felt queer jest then, and thought over all my sins, with the arrers stickin in my belly and back like all git out. I tried to pray ; but I'd never larnt no prayers when a pup, and now I was too old a dog to ketch new tricks ; besides, it was so all-fired cold, that my thoughts stuck in my head like they was pinned thar with icykels.
From Yankee-notions, volume 5 (1856[?]) [combined snippets]:
See—'tel you how 'twas: our Betsy Ann, she rote some verses for the paper here, the "Prairie K'dunk Banner," and some how or nuther the printer didn't take a notion to print 'em, but egscused himself by sayin' "respectfully declined"—you know how they do them things, perlite as all git out! Wal, Bill 'lowed there was a chance for a fite ; so he goes to the printin' orfice, and begins cussin and swarin, and sayin the chap could take his choice, to print them verses or fite ; well, he took his choice mity quick ; and the first thing Bill recollected he was a layin' in a corner on a pile of old types, and the devil a dancin juber in the pit of his stummick.
From James De Koven, "The Dorchester Polytechnic Academy—Dr. Neverasole, Principal," in The Church Register (November 1869):
"...There was a fellow here once by the name of Billy Edgar, he's a passed midshipman in the navy now, and he was up to all sorts of tricks. What a time we had when he stole old Jollipop's spectacles! And one day when everybody was looking for them, in walked the cat into chapel with the spectacles tied onto her nose, shaking her head and mewing like all get out. Old Mr. Howler stopped in the midst of his sermon on the Prodigal Son, and there was a row."
And from Emerson Bennett, The Outlaw's Daughter: Or, Adventures in the South (1874):
"Certainly a bold and dangerous proceeding!" said Miss Brandon.
"Ticklish as all git-out, I tell you!” chimed in the Yankee [Caleb Stebbins].
“Consarn it all, this ere hurts like all git out!” I next heard spoken, in the well-known voice of Caleb Stebbins. “ I say, you—Miss Flora—can't you jest let one of them are fellers loosen this ere cord a bit? It's putting my arms tu sleep—I snum, it is—that's a fact!"
An Elephind search of newspaper databases turns up a number of additional matches, including two from the late 1850s. From "A Fourth of July Visit ter Bostun!" in the [Indianapolis] Indiana Daily Sentinel (August 18, 1858):
Then the man behind the counter handed me a glass o’ sunthin' that smelt strongern all git out ur some sort o’ licker, an' says he: "You jest swaller down this little snifter o' pure skeedam kerchitooate without stoppin' to bite it off, then open your eyes tight, an' if you don't see the elephant, my name ain't Ralph Rattletrap."
And from "Fairs," in the [Clarksville, Texas] Standard (December 31, 1859):
Oh! such a place as that fair was. Acres and acres of ground fenced in with boards, and all strung over with white tents, and red flags, and sheep pens, and men in regimentals, and women in flounced petticoats. The wind blowed like all git out, and there was dust enuff to plant beans in. VVe got some pieces of yaller paper—give twenty-five cents apiece for 'em—and three pieces of ribbon, to pin to our shawls, that said we might gwin, and with Ichabod atween us, in we went.
All of these examples are from North America, and they suggest that the expression was well established by the time Mark Twain used it.