Iron can oxidize to "rust" (which is actually a mixture of hydrated iron(iii) oxide $\ce{Fe2O3*nH2O}$ and iron(iii) oxide hydroxide $\ce{FeO(OH)}/\ce{Fe(OH)3}$). The iron hydroxide species look like they could come from basic solutions.
Even if consider only the formation of $\ce{Fe2O3}$, this can occur by several pathways.
Using Wikipedia's Standard electrode potential data page as a source of known redox half reactions, the process may be something like this:
In acidic medium
The net reaction in acid is between the iron and the protons in the acid to produce $\ce{Fe^{3+}}$, which reacts with water in a redox neutral (but generates more acid) process to form the insoluble oxides/hydroxides. The initial redox reaction is spontaneous. The water is the net source of oxygen.
$$\ce{2Fe(s) + 6H+(aq) - 2Fe^{3+}(aq) + 3H2(g)} \ \ E^\circ=+0.04\ \text{V}$$
$$\ce{Fe^{3+}(aq) +3H2O -> Fe(OH)3(s) + 3H+(aq)}$$
$$\ce{Fe(OH)3(s) -> FeO(OH)(s) + H2O}$$
$$\ce{2FeO(OH) -> Fe2O3 + H2O}$$
In basic medium
The net reaction in base is between oxygen (in the air, which is not in contact with your submerged nail) and the iron in the nail. The iron initially reacts with the hydroxide ions, which are regenerated by the reduction of oxygen at the surface of the water.
$$\begin{align}
\ce{4Fe(s) + 8OH- &-> 4Fe(OH)2 + 8e-} \ \ \ &&E^\circ=\pu{+0.89 V}\\
\ce{4Fe(OH)2 + 4OH- &-> 2Fe2O3 +4e-}\ \ \ &&E^\circ=\pu{+0.86 V}\\
\ce{3O2 + 6H2O + 12e- & -> 12OH-}\ \ \ &&E^\circ=\pu{+0.40 V}\\ \hline
\ce{4Fe(s) +3O2(g)& -> 2Fe2O3(s)}\ \ \ &&E^\circ=\pu{+1.95 V}\\
\end{align}$$