Not Japan! We already have millions of Ninja games already, and Feudal Japan is always being used as a setting in games. The great thing about the Assassin's Creed is the way it picks uncommonly portrayed, yet fantastic settings. I don't think Fuedal Japan had much in the way of a scaleable skyline either. Besides the occasional pagoda, most of it would be one/two story buildings. Not interesting in the slightest. China would have a similar problem (though not as bad).
From the list, the British Empire makes a lot of sense. The spreading Empire would give liscense one character to explore many different locations. The American Revolution in one game, and India the next. ( Jodhpur [http://novapolis.free.fr/photography/india/jodhpur_med.jpg] should really be the next Assassin's Creed setting - but then that would mean making a game about Indian people, something which no Western(or Japanese) dev would ever dare consider).
Another advantage of Victorian, or better yet, Georgian England is that although guns have become the primary weapon of armies around the world, they aren't developed to the point of having too much accuracy, so cover mechanics won't be required. Once submachine guns and decent rifles enter a setting, you have to kiss goodbye to the free running.
I also quite like the sound of the Russian Revolution. The early period and the lack of guns would mean that the free running would still make sense. Not sure the cities would provide a fun free running experience though.