The outside of an atom, as it interacts with the rest of the universe, is it's electron shell. That is not a solid shell, but more of a fog of probability on where an electron (or usually multiple electrons) can be.
Since we cannot even ascertain where the electron is at any point, it is obvious it is NOT always anywhere. In fact, the atoms will actually 'share' electrons.
If the electron shell is mostly (almost entirely) empty, and so is the shell of the next atom over, even in the most dense material, it follows that the atoms are not actually touching.
In reality, all that keeps the atoms in 'contact' is their electrical and other forces, but at no time do they really touch anywhere.
Since they don't touch, it follows again, that there is space between them.
QED (without going into quantum physics)