Why don't things get destroyed by gas molecules flying around?

Things actually do get destroyed by what those air molecules pick up and throw around.

Take look at this example

[image from here: http://en.wikipedia.org/wiki/File:Arbol_de_Piedra.jpg ]

Just like their bigger sized brothers, it's the load of those mini-torpedos that brings the destruction.

Another way of looking at this is that things that would be destroyed by the environment likely already have been destroyed, unless you happen to catch them right at the moment they are being destroyed. The things that you see around you are the ones where the bond energy was high enough that they survived.

To take an analogy, consider the difference between comets and asteroids. Comets spend most of their time far away from the sun, so they are more likely to contain material that would decompose if brought near the sun, resulting in the comet tail. Asteroids, on the other hand, stay a more constant distance from the sun, so any material they might have had once that was susceptible to decomposing has long since disappeared. We say comets are "volatile," but it's just a matter of degree; asteroids would decompose too if they got much closer to the sun.

Or, another analogy, it would be like going up on a high mountain and asking why the animals there are able to survive the cold temperatures and thin air. Those animals are there because they are able to survive the conditions.

So, there are plenty of materials that would be destroyed by room temperature air. You're just unlikely to encounter them because odds are they would already be destroyed.

In fact, they do!!

Watch what happens to an ice cube that is left in the air... trillions of particles of its exterior are torn out of their stable arrangement, and soon they cascade down the sides—a microscopic waterfall!

So in this case you are right, but it is just the very exterior surface of an object that is exposed to the air and thus affected by it.

Remember that substances already at room temperature are composed of tiny particles which move at very high velocities. If this isn't enough to tear apart the substance, the air won't do much.

That said, I suspect that when one cuts through an object, the air molecules do in fact tear holes in the tiny peaks and crags on the newly exposed surface, until they are torn down and smoothed—but this would probably happen within milliseconds of being exposed to the air. I wonder whether doing this in a vacuum or in a more viscous medium like oil would change the effects.

Brionius has the right answer, but there is more to be said. Water at room temperature in air will slowly evaporate. Water at room temperature in a vacuum will boil, as is shown here. So these mini torpedos can prevent damage to chemical bonds.

Water molecules are polar. The O's are a little negatively charged. The H's are a little positive. The H's and O's are attracted to each other. Water molecules are sticky.

This is how ice forms. The molecules arrange themselves so that H's and O's are near each other and form relatively weak bonds. The molecules are vibrating at insane speeds. But at low temperatures, not enough to break the bonds.

At higher temperatures, the speed of the faster molecules is enough to disrupt bonds. The ice melts. In liquid water, nearby molecules still tend to arrange themselves so that H's and O's are near each other. This holds the water together as a liquid.

Air around the water also helps. Some of the faster molecules have enough energy to fly completely apart. They would, except that they promptly bump into air molecules. This helps hold the liquid together.

Exactly how well water molecules stick together is determined by temperature and pressure. In some cases, water does go directly from solid to gas. If the pressure is high, water remains liquid even at temperatures of hundreds of degrees. This happens on the ocean floor at volcanic hydrothermal vents.

This phase diagram shows behavior at different regions.