Oxygen Solubility in Water
Oxygen is relatively insoluble in water, its solubility being only 264 µM at 25 °C. That explains in part why you (and fish) require dedicated oxygen carriers in your blood to transfer sufficient oxygen around your body.
That oxygen is weakly soluble can be explained, as you point out, on the basis of the hydrophobic effect, which amounts to saying that water likes to hydrogen bond, and an oxygen molecule is not very good at that compared to another water molecule.
That oxygen is soluble at all can be explained on two grounds. First, statistics, just the random mixing of matter. Some oxygen molecules will happen to find their way into water and not find their way out for a while. The other explanation is that oxygen is not entirely nonpolar: it lacks a permanent dipole moment, but it is polarizable. Even molecules that we think of as highly water repellent can exist as liquids (oxygen is a gas at room temperature but can be cooled into a liquid state), which means something must be keeping them together, and that is dispersion forces due to the polarizability of all atoms and molecules.