You are confused about what the concept of infinity means. Infinity isn't a number that can ever actually measure a quantity of something, like resistance, because it's not a real number. As Wikipedia aptly puts it:
In mathematics, "infinity" is often treated as if it were a number (i.e., it counts or measures things: "an infinite number of terms") but it is not the same sort of number as the real numbers.
When we talk about an "infinite" resistance, what we are really considering is this: as the resistor gets arbitrarily large, what does something (current, voltage, etc) approach?
For example, we can say that as the resistance gets arbitrarily large, current gets arbitrarily small. That is, it approaches zero:
$$ \lim_{R\to\infty} \frac{15\mathrm V}{R} = 0\mathrm{A} $$
That's not the same as saying the current is zero. We can't ever increase R all the way to infinity, so we can't ever decrease current to zero. We can just get arbitrarily close. That means you can't now do this:
$$ \require{cancel} \cancel{0\mathrm A \cdot \infty \Omega = ?}$$
This is a bit of a mathematical contradiction by most definitions of infinity, anyhow. Most numbers, when multiplied by an arbitrarily large number, approach infinity. But, anything multiplied by zero is zero. So when you multiply zero by an arbitrarily large number, what do you get? I haven't a clue. Read more about it on Mathematics.SE: Why is Infinity multiplied by Zero not an easy Zero answer?
You could ask, as the current becomes arbitrarily small, what does the resistance approach?
$$ \lim_{I\searrow 0} \frac{15\mathrm V}{I} = \infty \Omega $$
However, if you look closely, you will notice that if \$I = 0\$, then you are dividing by zero, which is your hint you are approaching something that can't happen. This is why we must ask this question as a one sided limit.
Leaving the realm of mathematics, and returning to the realm of electrical engineering, what do you really get if you remove the resistor from that circuit, and leave it open? What you have now is more like this circuit:
simulate this circuit – Schematic created using CircuitLab
C1 represents the (extremely small) capacitance between the two wires that aren't connected. Really, it was there all along but wasn't significant until the resistance went away. See Why aren't wires capacitors? (answer: they are) and everything has some capacitance to everything else.
This really is not a black and white question and many folks will argue it does not follow "Ohm's Law", and depending how you argue it, they can be right.
However, the truth is the resistance of a diode changes depending on the applied current or voltage. As such, you can not simply look up the resistance of a diode and use "Ohm's Law" to determine the relationship between voltage and current by the good old V=IR formula like you can with a resistor. From that argument, no a diode, or more accurately, semiconductor, does not seem to follow Ohm's Law.
However, if you have a circuit with a diode in it, biased at voltage V or with a bias current of I, the resistance of the diode under those conditions is still a constant. That is, Ohm's formula still applies when the diode is in a steady state. If you are trying to calculate the output impedance of your circuit in that state, that is important to know, while acknowledging the impedance will be different when the circuit is in a different state.
In fact, I would go as far as to argue that a diode always follows Ohm's formula. Yes V=IR. However, in the case of the diode R follows a rather complex equation that includes V or I as variables..
That is for a diode
\$V = I.R_D\$ Where
\$R_D = F(I,V)\$
\$V = I.F(I,V)\$
So yes, mathematically, it does follow Ohm's formula, just not in a form that is much use to you except under very specific static conditions.
For those that argue "Ohm's Law does not apply if the resistance is not constant" I am afraid that is a misquote by Maxwell. Ohm's intent with that was that the resistance should be constant with time under stable excitation conditions. That is, the resistance can't change spontaneously with no change in the applied voltage and current. The truth is, nothing has a fixed resistance. Even your humble quarter watt resistor will change resistance when it warms up and as it ages.
If you think this is just he opinion of one man, you would be right, his name is
Georg Simon Ohm
Chances are you have never actually read his work, or if you read German, the original version. If you ever do, and, at 281 pages or antiquated English and electrical terminology, I warn you, it is a very hard thing to read, you will discover that he indeed covered non-linear devices and, as such, they should be included in Ohm's Law. In fact there is a whole Appendix, some 35 pages, devoted entirely to the subject. He even acknowledges there were things to still be discovered there and leaves it open for further investigation.
Ohms Law states.. according to Maxwell..
"The electromotive force acting between the extremities of any part of a circuit is the product of the strength of the current, and the resistance of that part of the circuit."
That however is only part of Ohm's thesis and is qualified in Ohm's words by the statement, "a voltaic circuit... which has acquired it's permanent state" which is defined in the paper, and I paraphrase, as any element whose resistance is dependent on the applied voltage or current or anything else must be allowed to settle into it's balanced condition. Further, after any change in the excitation of the circuit as a whole, a rebalance must occur before the formula is effective. Maxwell, on the other hand qualified it as, R must not change with V or I.
That may not be what your were taught in school, or even what you have heard quoted or read from many reputable sources, but it is from Ohm himself. The real issue is many people perceive or understand only a very simplified interpretation of Ohm's thesis, penned by Maxwell, that has been, possibly mistakenly, propagated over the decades since the great man actually performed his work as "Ohm's Law".
Which of course leaves you with a paradox.
The fact is Ohm simply stated, once it settles into a stable state the voltage across the circuit is the sum of the current times the resistances of the parts.
simulate this circuit – Schematic created using CircuitLab
\$E = I.R1 + I.R2 + I.R3\$
Where R3 is whatever resistance the diode settles into. As such, it does not matter whether R3 is a diode or not. Which of course is correct. Maxwell, on the other hand, implies that since the circuit contains a non-linear element, the formula does not apply, which of course, is wrong.
So do we believe what Maxwell wrote was an error in oversimplification and go with what Ohm really said, or do we throw away what Ohm really said and go with Maxwell's simplification which leaves non-linear parts out in the cold?
If you believe a diode does not fit your mental model of Ohm's Law, then your model of Ohm's Law is actually Maxwell's Law. Something that needs to be qualified as being a subset of Ohm's thesis. If you believe a diode does fit the model then you are really quoting Ohm's thesis.
As I said, it is not black and white. In the end, it does not really matter since it changes nothing.
Best Answer
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. :-)