Excellent question Brian, and fine responses from others- this is why I love lurking on Phys-L.
Methinks G can have been estimated. First, it is interesting to note that Eratosthenes estimated the size of the Earth approximately 250 BC. (There's uncertainty about how close he came- somewhere between 1% and 20%- which is pretty good using shadows and the average lope of a camel! Eratosthese found the circumference to be about 250,000 stadia, and there's disagreement about the length of a stadia...er, stadion?)
So Earth's approximate radius R has been known for a long time. And g at the Earth's surface is approximately 10 m/s^2.Further, g = GM/R^2 and, of course M equals the average density of the Earth times the volume of a sphere. Thus, one can easily obtain a relationship between surface g, average density, and R. Rock densities run about 3000 kg/m^3 and this will yield G on the order of 10^-10 or so, depending on one's value for R... of course, the Earth's average density is closer to 5500 g/m^3.
But it's still nice to realize that one could get within about an order of magnitude with Eratosthenes result and an average rock density. Fun! Thanks colleagues!