Just as the title says — where, and how, did the phrase 'stone the crows' originate?
Etymonline offers no insight. The British National Corpus has three cites from 1989, 1991, and 1992. The Corpus of Historical American English has two cites, from 1981 and 1986. Wiktionary doesn't say anything about etymology, but marks the phrase as UK, Australian, and has a much older cite from Rose Of Spadgers by C. J. Dennis, 1924. The most extensive discussion I have found so far is over at The Phrase Finder:
Partridge also lists "starve the bardies or lizards or mopokes or wombats", marking them all as Australian expletives, and noting that "Wombats may also be speeded".
I believe it is "soundalike" - like how Cor Blimey sounds like "God Blind Me" (in certain accents) - for "Christ on the cross". If you didn't say the "cry" part, the rest pretty much matches. I base this on the habit of various elderly male relatives of mine from England to actually say "Christ on the cross" when they hit their thumb with a hammer or other situations that needed lots of syllables to indicate your sweariness. ("Jesus, Mary and Joseph" was also a good one for those times.) Seems these days we just say the same swearword 6 times instead of extending to a phrase, so having substitutes for the phrases may not make sense any more.
Reference book coverage of 'stone the crows'
Here is the entry for "stone the crows" from Nigel Rees, A Word in Your Shell-like (2004):
Other recent reference works confirm much of Rees's description. And from Robert Allen, Allen's Dictionary of English Phrases (2008):
And from Max Cryer, Curious English Word and Phrases (2015):
Google Books search results
A Google Books search finds a match for "stone the crows in Lincoln Hulley, A Farmer Prince (1925) [combined snippets]:
This appears to be a literal use of the phrase,and Hulley lived his entire life in the United Sates, far from Australia the locus of early uses of "stone the crows" as an exclamation.
The next-earliest Google Books match is from Australian Parliamentary Debates (the exact date of the quotation is unconfirmed, but Google Books says that this volume of debates was published in 1931) [combined snippets]:
Norman Makin was speaker of the Australian Parliament from November 20, 1929, until February 16, 1932, so the 1931 date of these debates appears to be pretty firm.
The next-earliest match is from Robert Thompson, Down Under: An Australian Odyssey (1932) [snippet]:
The earliest Google Books match for "stiffen the crows" is slightly later than these results for "stone the crows." From Michael Terry Untold Miles: Three Gold-Hunting Expeditions Amongst the Picturesque Borderland Ranges of Central Australia](https://books.google.com/books?id=xEtCAAAAIAAJ&q=%22stiffen+the+crows%22&dq=%22stiffen+the+crows%22&hl=en&sa=X&ei=DZb6VMjROszboATK14CwBw&ved=0CCEQ6AEwATge) (1933) [snippet]:
As Rees points out in A Word in Your Shell-like, "starve the crows" may be the oldest term for denying crows access to crops by chasing them away and throwing stones at them, as mentioned in Alan Gulston, Warren Knowles, volume 2 (1885):
An article in Geographical Magazine, volume 21 (1948) [combined snippets] lists some other allied expressions in the greater contrast of saying that invoke Australian animals:
"Stone the crows" comes from an actual event which happened in the late 1800s, just south of Roebourne in Western Australia.
A teenager who was part of the original white settlement there was becoming exasperated with the flies and the heat and in a moment of temper he picked up a stone to throw at a crow. As he was about to throw the stone, he stopped in his tracks because the stone was too heavy for its size. On inspection the stone contained a large proportion of gold. The term "stone the crows" traditionally translates to, "well how about that". The event is recorded in a book about the North West which was written in the 1930s. I have a copy of the book in my library if anybody wants more details.
Perth Sunday Times 1929 - here it is in print . http://trove.nla.gov.au/ndp/del/article/58384974