+1 on Cuchulain and Gilgamesh
Honestly, I think you're being unnecessarily restrictive in your approach. If I were so inclined to do such a campaign, I'd probably open it up to my players, w/ a list as some guidance, and let them bring me the info about the reincarnated heroes they want to play, they should be willing to pitch them. Also, since you're willing to say that these are the "real world" versions of mythical characters, things don't have to literally track the mythology. There are, as people have suggested, several ways to build an Achilles who is resistant to damage (and, again, that's sort of the player's problem ...), but even if you just gave him an astronomical AC or something the people would probably feel like he was invincible; viz. the flawed film "Troy."
Also, I'm not sure how I'd approach the strong hero/villain dichotomy. These characters, especially the older you go, are almost always flawed and often tragic heroes, but (1) they are heroes nonetheless and (2) they are interesting. Achilles is an almost unimaginable douche, Lancelot touches off a conflict that essentially rekindles a civil war and an age of darkness that they just recently got out of, Hercules strangles his wife and child (under supernatural influence, but the Greeks were less understanding about that sort of thing), Alexander might have murdered his own father, and so on. Moreover, a lot of them operate in a foreign morality -- I played a mythic Greece game, and there it's ok to rape, murder, and enslave people, but being rude to a host is a crime worthy of divine punishment. Go figure.
Which is all to say that I could totally see someone playing the reincarnation of Genghis Khan or Rasputin as a hero, perhaps a flawed (e.g., overly ambitious, temper).
Oh, and I'd suggest Tamerlane (also called Timur) as a great villain, and one a bit less famous than the others.
Btw, this sort of reminds me as a more epic version of "Riverworld," if you're familiar w/ it.