Don't know if you're still taking ideas, but Bokurano has destroyed cities back and forth! You could also try Wolf's Rain (apocalyptic vibe) and the Pandora Hearts story centers around a city that was destroyed, and there is footage of cities being destroyed near the end.
Fist of the North Star is prettymuch a given here. Also, while dubious on its merits as an anime, M.D. Geist may get you where you need to go footage-wise.