How does oil on the surface of water prevent rust? I distinctly remember a side-by-side comparison from a book where there are two nails submerged in water, in two beakers: one nail had a layer of oil on top of the water, and that nail didn't rust; the other did. 

It seems that oiling iron/steel products is supposed to prevent them from rusting: 
http://www.justanswer.com/home-improvement/0n1r2-does-olive-oil-prevent-rust.html
https://outdoors.stackexchange.com/questions/1404/can-oiling-keep-tools-from-rusting

The explanation given, I think, is that the oil somehow prevents oxygen from reacting with the metal. 

Can't help but wonder why. Oxygen is a non-polar molecule, so it should actually dissolve better in oils (which are also non-polar) than in water (which is highly polar) and therefore allow more oxygen molecules to contact the iron (metal) surface in some sort of equilibrium. 

Let's say that the conductivity of water and its ability to form electrochemical chains between metals is irrelevant in this thought experiment (i.e., a nail submerged in water in a glass). From what I understand, the other key item that has an effect on the formation of rust in water is that the oxygen molecules have better contact with the iron surface. 

This is supported by data: the concentration of oxygen in air is far higher than that in water. We know from experience, though, that wet iron rusts way quicker than dry iron does. 

If I am reading it correctly, the same data shows higher oxygen concentrations in non-polar solvents than in water. 

Here is the data: http://www.nist.gov/data/PDFfiles/jpcrd219.pdf 

Please correct me if I am reading it wrong. 

My question is:

How does oiling prevent rust? 

Edit: For the sake of clarity, let's say we use deionized water in a vacuum, drop in the nail, then put some oil (let's say it's caprylic acid) on it, and expose it to standard conditions.
Well, I went and searched for the solubility of oxygen in water and oil, and found this summary paper on the NIST web site: "The Solubility of Oxygen and Ozone in Liquids" by Battino, Rettich and Tominaga, J. Phys. Chem.Ref. Data., vol 12, no. 2, 1983.

Conveniently, the paper gives solubility data for oxygen in both water and olive oil.  The solubility is given both as molar fractions, and also as the Ostwald coefficient $L$, defined as the volume of gas absorbed per volume of absorbing liquid.

Given the very different molar volumes of water and olive oil, I believe the latter provides a much more useful comparison here.  Comparing tables 1 (water; note the $10^2$ factor in the header) and 25 (olive oil) in the paper, we see that the Ostwald solubility coefficient for oxygen in water is about 2,000 times higher than in olive oil:

 Temp. (K) | Temp. (°C) | L (water) | L (olive oil)
-----------+------------+-----------+---------------
    298.15 |         25 |     310.4 |        0.1269
    308.15 |         35 |     276.6 |        0.1326
    318.15 |         45 |     254.5 |        0.1383
    328.15 |         55 |     240.9 |        0.1441


So, yes, oxygen is a lot more soluble in water than in oil.  But why?

Well, if this web site is to be believed, it's because of the strong hydrogen bonding between water molecules, which causes even liquid water to maintain some degree of an ice-like lattice structure, with gaps that small gas molecules like $\ce{O2}$ can easily slip into.  Once there, the gas becomes solvated, with the strongly polar water molecules inducing a temporary dipole in the $\ce{O2}$ molecule and thus creating an attractive Debye interaction.  The overall solvation process is exothermic (i.e. releases heat), explaining why the solubility of oxygen in water decreases with temperature.