Ohm's Law confusion -- can there be voltage without current?

Your estimate is off by several orders of magnitude. Wikipedia gives the resistivity of air as being around \$10^{16}\ \Omega \cdot m\$. I'd guess an actual resistance between two points would be at least on the order of teraohms. Assuming \$1\ T\Omega\$, that gives a current of 5 picoamps, which is far too small to measure easily. As pointed out in an answer to another EE.SE question, the material the battery is made of is probably a better conductor than air.

To actually figure out what's going on in extreme situations, you need a more detailed model of the materials involved. How many electrons and/or ions are available for conduction? An ideal dielectric (insulator) has no free electrons, but a real dielectric might. What's the strength of the electric field? If you have a 40 kilovolt voltage source, you can rip apart air molecules, creating lots of free electrons! A less extreme example would be a vacuum tube, which "conducts" through empty space \$(R = \infty)\$ using electrons liberated from a piece of metal.

Ohm's law is an approximation that works for many materials at low voltages, frequencies, and temperatures. But it is far from a complete description of electrodynamics and physical chemistry, and should not be treated as such.

To answer your question more directly, regardless of whether a tiny current flows through the air, there can definitely be a voltage between the terminals. Voltage is another way of describing the electric field. Wherever there is an electric field, there is a voltage difference, even in a vacuum with no matter at all! HyperPhysics shows what this looks like.

Specifically, the gradient of the voltage field gives you the magnitude and direction of the electric field:

$$\vec E = -\nabla V$$

I don't know whether a tiny current actually flows through the air, but hopefully now you have a better appreciation for the physics of the situation. :-)

The voltage across the (ideal) battery is independent of the current through. That is to say, the battery is not an ohmic device and thus, does not 'obey' Ohm's law.

In other words, the voltage across the (non-zero) resistance is fixed by the battery; that voltage is given and is independent of Ohm's law.

Since the voltage across the resistance is fixed, the current through is determined by Ohm's law.

Thus, for an (ideal) open circuit (the limit as \$R \rightarrow \infty\$), the current through is zero but the voltage across is fixed by the battery voltage.

In summary, the voltage across the resistance (in this ideal circuit) is not determined by Ohm's law, it is determined by the battery. When the resistance is 'infinite', the current through is zero by Ohm's law.

Note that there is difficulty if we allow the resistance to go to zero. In the ideal case, the current is unbounded. However, this isn't physical. A physical battery cannot supply unlimited current (there is an effective internal resistance) and so, to model this, we add a small resistance in series with the battery.

Open circuit means infinite resistance.

So: $$ V = I\times R = 0 \times \infty$$ and

$$ 0 \times \infty$$ is not defined.
See: Why is Infinity multiplied by Zero not an easy Zero answer?