I easily outexpand the AI in Warlord. I can hold pace, and depending on the map/geography/capital proximity, outexpand the AI on Regent. I thought it was impossible too, but i tried strat or two, refined them, and now i have it down.
found a city, build -- warrior, warrior, settler, warrior, settler, spearman, settler, temple, settler, worker, settler, etc
until you have the place filled. you should have enough roaming warriors to reign in the AI at any bottlenecks, and keep those roaming settlers safe from barbarians by patrolling the area, wiping out camp after camp. you should also have enough workers roaming around, improving and roading so that you actually start really pumping them out.
City placement is key -- since you build that temple kinda late (it takes great restraint for me to wait even that long) you need to leave enough space for the cities to expand, but not so much that the AI can infiltrate in. If you get a checkerboard border, youll have cities flipping left and right. Once your cities expand once/twice, youll see the holes -- usually on your coasts -- wehre hte AI will put a city. Dont worry about them, culture rush them out of the way, or station troops and when you war against your immediate neighbor (usually in the middle ages for me -- i have trouble ramping up for war fast enough in Ancient) you can take those cities out without so much as a scratch..
happy expansion!