Usually with the AI's main army running around between cities, I'll have my army (usually substantially smaller because I was researching adventuring or something) pop into an enemy city with little resistance, destroy all the buildings with the shovel, and then pop out of the city the same turn and get out of Dodge before the enemy AI can counter-attack.  If the enemy AI's main force does happen to be in a city I'm attacking, I just cancel the attack and then head to a different city.  Rinse and repeat with these guerilla attacks until all enemy cities are razed to the ground.