Now, a new book called The Golem Returns by Cathy S. Gelbin has found an earlier source from 1834. What's particularly awesome about this is that this source was sitting right there on the pages of the Jewish Encyclopedia for more than 100 years.
Here is a sample, and below it is the entire document in Scribd.
As you can see, this is from Sulamith v.8 (which is available at compactmemory.de). It's described as a "Prague Legende,"and it is titled Der Golem und die Ehebrecherin, which means The Golem and the Adulteress. This piece is by Gustav Frankl, who was already known for his version of the legend - but it had been published in 1841. The Jewish Encyclopedia erroneously says that this earlier source is "abridged" from the later one, but there can be no doubt, 1834 is 1834, and it is about Rabbi Lob and his Golem.
Eli Eshed, a golem researcher, gets the credit for calling attention to this new book, which I have not yet seen.
EDIT 3/4/11: Important update. This is a mistake. Please see this post, where I give an actual 1834 source for the Golem.