The concept of empty space is actually quite tricky, since our intuition "Space is empty when there is no particle in it" differs from the formal "Empty"Empty space is the unexcited vacuum state of the theory" quite a lot. The space around the atom is definitely not in the vacuum state, it is filled with electron states. But if you go and look, chances are, you will find at least some "empty" space in the sense of "no particles during measurement". Yet you are not justified in saying that there is "mostly empty space" around the atom, since the electrons are not that sharply localized unless some interaction (like measurements) takes place that actually forceforces them to. When not interacting, their states are "smeared out" over the atom in something sometimes called the electron cloud, where the cloud or orbital represents the probability of finding a particle in any given spot.
This weirdness is one of the reasons why quantum mechanics is so fundamentally different from classical mechanics -– suddenly, a lot of the world becomes wholly different from what we are used to at our macroscopic level, and especially our intuitions about "empty space" and such fail us completely at microscopic levels.
Second, consider the situation of two equally charged classical particles: If you only invest enough energy/work, you can bring them arbitrarily close. The Pauli exclusion principle prohibits this for the atoms -– you might be able to push them a little bit into each other, but at some point, when the states of the electrons become too similar, it just won't go any further. When you hit that point, you have degenerate matter, a state of matter which is extremely difficult to compress, and where the exclusion principle is the sole reason for its incompressibility. This is not due to Coulomb repulsion, it is that that we also need to invest the energy to catapult the electrons into higher energy levels since the number of electrons in a volume of space increases under compression, while the number of available energy levels does not. (If you read the article, you will find that the electrons at some point will indeed prefer to combine with the protons and form neutrons, which then exhibit the same kind of behaviour. Then, again, you have something almost incompressible, until the pressure is high enough to break the neutrons down into quarks (that is merely theoretical). No one knows what happens when you increase the pressure on these quarks indefinitely, but we probably cannot know that anyway, since a black hole will form sooner or later)
So, in conclusion, one might say that at the levels of our everyday experience, it would probably enough to know about the Coulomb repulsion of the electrons (if you don't look at metals too closely). But without quantum mechanics, you would still wonder why these electrons do not simply go closer to their nuclei, i.e. reduce their orbital radius/drop to a lower energy state, and thus reduce the effective radius of the atom. Therefore, Coulomb repulsion already falls short at this scale to explain why matter seems "solid" at all --– only the exclusion principle can explain why the electrons behave the way they do.