Studies of surviving hunting-gathering societies suggest that their lives were much lower stress and life spans (barring violent accident) much longer than early agricultural societies. Even with accident included, their lifespans were better comparatively recently. (For instance the eskimos, despite living in one of the harshest environments on Earth, had about a 25% chance of surviving to 60.)
Whether or not they would lose their teeth varied by diet. Our diets have lots of sugar and grains in them which promotes tooth decay. Other diets differ. Early surveys of eskimos that had never eaten Western food showed that most never have had a cavity in their lives. The immunity was not genetic - those exposed to Western food had plenty of cavities.
See http://wholehealthsource.blogspot.com/2008/07/mortality-and-... for a reference to the lifespan of eskimos. See http://www.journeytoforever.org/farm_library/price/price5.ht... for some evidence about their lack of tooth decay.
The primary reasons to brush your teeth are to prevent cavities, plaque buildup, and smell. If you don't get the first problem, the others are easy to ignore. Pleasant smelling breath is a modern ascetic, so it's easy to imagine a scenario where a young man that hasn't had regular intimate contact yet ignores the bad breath. It's only afterword that the positive social benefits become understood.