Gerald Cohen, an etymologist at MS&T (Missouri Science & Technology, formerly University of Missouri at Rolla), has investigated this.
The Congressional quote, while genuine, was clearly the kind of statement that wouldn't make a lot of sense if the statement weren't already a meme (of sorts). Sure enough, Mr. Cohen found numerous references in print prior to the congressional statement in question.
Curiously, he didn't find one printed prior to 1894, but found several from that year. They still tend to read as if the audience knows some unprinted context behind them, so its probably something that was a word-of-mouth meme for a while prior to it becoming a popular printed meme in 1894.
One alternate popular etymology is that it had to do with ignorant miners imported to Colorado from the Ozarks needing to be shown how to do the job properly. This explanation has a few things going for it logically, but we don't really have the kind of evidence that could make it more than just another story.
One thing that is a fact is that the earliest references we have for it came from a newspaper in neighboring Omaha, Nebraska (The World-Herald). He found it used there 3 times in 18941, again in 1895, and again in 1896. He didn't find it used by anyone else prior to 1897. References to resident Missourians themselves starting to claim it begin to appear in 1898.
As far as we know, here's Patient Zero for the meme:
(John S. Johnson, a bicycle rider --ed.) says that he can cover a mile
in 1:30 flat, but being from Missouri he will have to show me.
(28 October 1894, Sunday World-Herald (Omaha, NE), pg. 10, EATON)
There was perhaps also a cultural dimension to this. Under the Third Party System, Nebraska at the time was reliable Republican territory, while Missouri was reliable Democratic territory. The Democratic coalition at the time was essentially White Supremacists, immigrants (largely Catholics), unskilled laborers, and poor farmers. The Republican base was more skilled workers, businessmen, and better-off farmers. So one could see how the latter might tend to look down on the former.2
If we use Occam's razor on all this, it looks like the simplest explanation fitting the facts we have is that it started as a fun in joke with the readers of the Omaha World-Herald at the expense of their Southeastern neighbors, perhaps even with the very quote above.
1 - Coincidentally (or not?) this was the same year future populist Democratic presidential candidate William Jennings Bryan became editor of this paper.
2 - Wikipedia today will tell you this system ended with the election of 1892, prior to the "Show Me" meme. However, these two states in particular didn't both settle on their new Fourth Party system alignment until the election of 1904.