While I will agree that our bodies do not function best on a meat-based diet, to say we evolved as vegetarians is not correct. During the Australopithicene era, two lines diverged -- one, the "robust" line, evolved stronger jaw musculature (and skull crests to accommodate those muscles) for extracting more nutrition from a solely vegetarian diet. The other line, which ultimately led to the genus Homo, were the "graciles" who, rather than evolving to better process plant foods, were incorporating animal foods (typically believed to be scavenged remains from other predators) which were more calorie-dense and included nutrients necessary for greater brain development (our brain is the largest consumer of calories per volume in our body). Additionally, lacking the saggital crests (seen today most prominently in skulls of gorillas, who are more strictly vegetarian than chimpanzees) allowed for our skulls to expand more readily as we matured, to accommodate a larger brain.
As for our intestinal system, it does not most closely resemble that of herbivores, who typically have some sort of "fermentation chamber" allowing greater efficiency of cellulose breakdown. Our intestinal system actually very closely resembles that of the pig in terms of large and small intestine proportionate to our body mass. And pigs are known to commonly incorporate animal protein (yes, even scavenging carcasses) in the wild.
I think there might be some confusion over the definition of the term "herbivore" versus "carnivore" and "omnivore." "Herbivore" does not mean the same thing as "vegetarian." A herbivore extracts the majority of its calories from "herbage" or leaves (browsers) and/or grasses (grazers). Herbivores are vegetarian, but not all vegetarians are herbivores. There are also granivores (grain or seed eaters) and frugivores (fruit eaters). "Omnivore" often equates to something that eats meat and vegetables, but really means eating virtually anything that could be food. Omnivores are not as efficient at metabolizing plant material as herbivores/granivores/frugivores, but are better at it than are carnivores. And even within carnivores, there are degrees. Obligate carnivores (cats, for example) cannot prosper without meat, whereas opportunistic carnivores (most bears, for example) typically only occasionally eat meat.
Today, with the range of foods available due to agriculture, it is very possible for humans to be healthy as vegetarians as long as "healthy vegetarianism" is practiced (as in, not just removing meat, but adding other stuff). If someone ate crappily while also eating meat, simply eliminating the meat won't make the person healthy.
The "protein dilemma" is really not as serious as it seems. The typical American diet is way higher in protein than is necessary, anyway. I remember learning that for maintenance, one gram of protein per kilogram of body mass is the general guide. And it's been found that eating complimentary proteins (bean and grain, for example) does not need to occur in the same meal. Amino acids (protein building blocks) are stored in the liver for 24-48 hours if not immediately necessary.
Yes, soy is a "complete" plant protein, in that it contains all the "essential" amino acids (those we can't produce on our own) but not in the correct proportion. I don't remember which it is the lowest in, but whenever you are measuring consumed protein, the available protein for the body is dictated by the amount of the least-consumed essential amino acid. So if you need 20 units of each essential amino acid, and have 20 for all but one, of which you consumed only 10, then your available complete protein is only 10 units. So if you eat a lot of soy, you still need to be getting additional protein from non-legume sources. And there are other "complete protein" foods that aren't from animals. Quinoa and/or amaranth (both are grains) come to mind at the moment, but I can't remember which or if both fit the bill.
Soy digestibility is made possible by heating the bean (or whatever form it is in) to deactivate the protein-inhibiting molecules (can't remember the name off the top of my head....long day). Oh, and by the way, a lot of the "soy controversy" was promoted by the various meat and dairy industries, typically using soy that had NOT been heated before feeding to test animals for their nutrition trials. And to those who say men eating soy will lose virility and have lower sperm counts, I ask how is it that soy has been consumed in Asian cultures for centuries, and there's no shortage of Asian people?
I believe one can be healthy AND eat meat, though not to the degree of consumption promoted in American culture. Eating meat and animal products was seen to be a sign of wealth and prosperity. After all, you have to feed an animal food that could be eaten directly by people, or grass that was grown on land that could have been used to grow human-edible food, which uses more resources per calorie. So I think that figuring out how to produce meat cheaply has been seen as a way to give the impression that America is a wealthy country. But cheap meat isn't healthy meat, and eating it more often because it's cheaper is not the way to go.
I eat a mostly vegetarian diet, but I do consume pastured meat a few times a month. It's more expensive, but in terms of my monthly food expenses, it still costs less to eat the way I do than to eat some kind of cheap meat at every meal. I try to eat food as close to its natural state as possible (more whole grains versus flour-based foods, plenty of veggies cooked simply such as by steam, saute or roasting, etc). I believe this most closely resembles the diet that works best for our bodies. But I'm no one special, so don't take this as some kind of proclamation that everyone has to follow. I'm just sharing my opinion based on facts I've learned over the years.