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.
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. :-)
Best Answer
This can only happen if you have an ideal battery. In the real world, nothing is ideal. You have an internal resistance of a battery, usually in the milliohm region, and you also have the wire shorting the battery out. That also has a resistance. What you have now done is created a circuit with resistance, and therefore current. You end up with something like this:
simulate this circuit – Schematic created using CircuitLab
This means that you will always have a voltage on the battery. The resistance will be very small, hence why there will be a lot of current flowing, which will mean a lot of power dissipated as heat, which is why it can be dangerous to perform such experiments!
As you can see, there is no such thing as a true short circuit, as there will always be resistance somewhere, no matter how small!
As for wrapping your head around voltage becoming non-zero when resistance is added... Well, you don't have to! For the zero condition to exist, the resistance must be infinite, if there was no resistance, then there would be no circuit!