Won Before 1000AD King

I done it with the Aztecs. I actually don't think it's possible not to use them. But I did it on King difficulty. It took me some tries but I did it. The thing was that the Greeks were always on the map. The Greeks are hard to take out early sometimes. I'd usually run into the Arabs or French and kill them with a fast Horsemen army. But when I get to the Greeks my ass would get handed to me. But what I did is hope that I get a Caravan or an early Spy and used them to explore the map. Once I found them I went for them first. They didn't have a Hoplite army but just Hoplites. After that you have to quickly research to get Mathematics for Catapults. Because they kept giving my Horsemen army meaningless upgrades like Medic and Guerilla. And I had the Romans who I knew had a good Archer army all fortified. I didn't want to waste my army and all the experience they had. So I built a Temple and converted the nearest city to the Romans. When I got Mathematics I built Catapults near the Romans and protected them and then declared war. It took a while but I got him.

When I explored all of the continent, I figured the last civ would be on a different one so I started to build a Galley. I put my Horsemen on the Galley. I also figured that the civ wouldn't be as militaristic as the Greeks, Romans and Zulus. I ran into the Indians and took them out with the Horsemen. I got the achievement and was actually surprised I pulled it off.