I think many of these settings would be cool in some game, but not necessarily in an AC title. While Egypt, Cambodia, time of the Spanish Inquisition, and Vikings era would be cool, I believe they lack high buildings, which combined with the climbing and leaps of faith, are an important part of the AC games (for me at least). And before people come up with "But the pyramids are tall ...", yeah I know, but the other buildings weren't high then, I believe.
Japan would be cool, as well. But I don't think feudal Japan would be in an AC game, because the AC titles have always progressed in time, except AC IV, but there you play Connors grandpa, so there's still a direct link.
Japan however would make sense in the late 1800's during the industrial revolution in Japan. Sort of like in "The last Samurai" the protagonist could be a Samurai and the Templars could be the ones bringing the newer technology to Japan. Something like that.
Russian Revolution would be awesome, IMO. Or maybe the time just after WWII as an Assassin, who hunts down German/Templar scientists who migrated to other countries or so. Maybe people like Wernher von Braun could also be Templars.