Just tried this at deity level. After a few false starts, my time between getting a horse/chariot from a hut (I didn't want to waste time setting up an entire game just to get that first hut) and defeating the last tribe (whereupon my game crashed since I'm using WINE) was 11:33.
I played against Celts (who didn't start in Britain), Zulus, Carthaginians, Persians, Indians, and French.
In all attempts, Babylonians would have a second settler mining a hill, which I couldn't get past. Carthaginians also had 2 settlers every time, so sending my settler to quickly conquer them didn't work.
My strategy was horseback riding, then Polytheism, then just money. Zulus were last to be defeated.
It occurs to me that if you're choosing the AI tribes, no player restarts, etc., you might as well just choose to play a game with 3 tribes instead of 7.
The idea of speed running Civ II has crossed my mind from time to time, but this setup doesn't really capture much of what makes Civ II interesting.