Historically, Isaac Newton was of course the first man who discovered the inverse square law and Coulomb just copied it from Newton. Electrostatic and gravitational fields both follow the $1/r^2$ law because in some regime, they're described by the same mathematical equation $\Delta \Phi = \rho$. In plain English, these laws indicate the field lines have to be shared by (i.e. diluted to) the area $4\pi r^2$ of a sphere which is why the intensity has to drop as $1/4\pi r^2$. This is really the "heuristic" explanation why the law is $1/r^2$ in a three-dimensional space. In a 9-dimensional space, it would be $1/r^8$ and so on.
Isaac Newton originally determined the inverse square law from two independent but closely related considerations, almost at the same moment. One of them was a comparison of the motion of bodies near the Earth and the motion of the Moon. The other one were Kepler's laws for planetary orbits.
Concerning the Moon-ball analogy, he could have figured out that the Moon is 60 times further from the Earth's center than objects on the Earth's surface (360,000 km vs 6,000 km). He translated this ratio to a ratio of the forces that must act on the objects at these two distances to yield the right ratio of periodicities, and figured out that the forces' ratio is 1-to-3,600 and the law is therefore $1/r^2$.
The other method – which is nearly equivalent (and mainly differs by having the Sun instead of the Earth as the source of gravity at the center) – used Kepler's third law. Kepler was able to deduce the exact orbits of the planets (including the timing) from Tycho Brahe's meticulous observations and extract the phenomenological laws. The third one says that $T^2\sim a^3$: the squared period of the orbit is proportional to the third power of the greater semi-axis of the elliptical orbit. When one studies circular orbits, it's straightforward to prove that this power law relating the period and the radius is equivalent to the $1/r^2$ power law in the force. You're invited to check it yourself; if you're missing some maths to do so, I am afraid that my reproduction of the proof wouldn't be any helpful, anyway.
Let me give you the derivation, anyway. The centripetal force (and acceleration), like the opposite centrifugal one, goes like $r\omega^2\sim r/T^2$ where $T$ is the period and $r$ is the radius of the circular orbit. Because Kepler determined $T^2\sim r^{3}$ in his third law, $r/T^2$ goes like $r/r^3=1/r^2$ and that's it: I derived that the acceleration (and therefore force) that has to act on the planet has to go as $1/r^2$.
(Note that if you wanted $1/r$, the third Kepler's law would have to say $T^2\sim r^2$ i.e. $T\sim r$. This proportionality would be equivalent to constant velocities of the planets, regardless of their distance from the Sun. That's indeed how things would work if space had 2 spatial dimensions but the real-world Solar System and similar systems just don't work like that: the speed of nearby planets is higher.)