Why are hydrogen ions always associated with another molecule?
The way I understand it is (and my understanding is by no means perfect, or complete), as you pointed out correctly: a hydrogen ion is in fact a proton. The proton is a "bare charge" and as you rightly said, "tiny". a
This makes it extremely reactive (in a sense), and thus in a chemical system of any sort would immediately seek out and associate with the electron clouds of a surrounding molecule. 

For instance, in an aqueous solution it forms $\ce{H_3O+}$ (hydronium ion, which are further solvated by water molecules and form a manner of aggregates).

An extremely interesting way of looking at it was pointed out in the comments (just putting it here, so no one misses it)


  An interesting way to thinking about the reactivity of a bare proton is to calculate its charge density and compare with other monocations, such as Li+. This will make it clear why free protons will abstract electrons from just about anything. –  Nicolau Saker Neto


Do note (as far as I know, someone might correct me if I am wrong) free protons are fairly stable (by free I mean not bound to electrons or other nucleons) and usually don't decay into other particles. They exist in several naturally occurring situations, high energy plasmas come to mind.