It is quite possible to examine diet through archeological means (composition of bones and teeth). However, I don't know that anybody has done a systematic study of such records with an eye towards looking for vegetarianism.
The one piece of similar information I am aware of is that teeth of hunter-gatherers are often discernible at a glance, due to the relative lack of cavities, due to their diets being far lower in carbohydrates. That's a grain issue, not a meat issue though.
If vegetarians were archeologically found, I'd think it would be nearly impossible to tell if it were by choice rather than lack of opportunity. We do know, based on tool sets, that some hominid cultures weren't slaughtering large game. That doesn't mean they weren't eating fish or snails though.
On a macro-genetic scale we do know the following:
Our closest relative in the animal kingdom is the Chimpanzee. Based on common traits, it would be reasonable to assume that our common ancestor (about 6 million years ago) was a creature that was omnivorous, including eating insects (perhaps occasionally with the help of crude tools), and occasional organized hunting parties for bigger game. Chimps (and hunter-gatherer humans) do all that today.
Around 2 million years ago there were multiple hominid species living, including Paranthropus Robustus and Homo Habilis. Panthropus was a big bruiser, resembling an ambulatory gorilla. While there's some debate about his diet, he does appear to have been specialized for plant eating. He had bigger molars, and bigger jaw muscles to deal with all the extra plant chewing. Habilis on the other hand, was a tool-using omnivore who probably would eat pretty much anything consumable he could get hold of. The Panthropus line died out, while the Homo line eventually evolved into Homo Sapiens.
Large scale cultivation of grains didn't happen until about 10,000 years ago. Skeletons of farming people are instantly recognizable for the dental damage caused by all those carbohydrates. This is still the case today, which indicates 10,000 years has not been enough time to evolve teeth better suited to this diet. One thing we can say is that our species was clearly not designed for the carbohydrate-heavy diet most people have been eating for the last 10,000 years.
So as far as the "optimization" of our bodies for our diet goes, you will probably need to look at our diet further back than 10,000 years ago. As recently as 2 million years ago, people (Genus Homo) were clearly the hominid species designed to be flexible omnivores.