Honestly I don't think that any of the options (aside from maybe the first one) would be good for a trailer.
This is my suggestion: http://www.youtube.com/watch?v=LRLdhFVzqt4Please read these as you listen to the song - I suggest opening them in windows next to each other.
(1) 0:00 - Fade in to a large, misty landscape (perhaps from the clouds). Flags flapping in foreground
(2)0:28 - High speed flyovers of large, impressive landscapes - straight flight, looking down - armies of bots swarming below
(3) 0:43 - Circle a castle on a hill. People/bots are visible moving and building on the walls.
(4) 0:56 - Camera begins at base of castle and moves up tower to the top. Archers/king visible on top of tower, looking outwards
(5) 1:10 - Sweeping panorama of land around castle. Army is beginning to form at the base of the hill, preparing to march at castle. Pan towards army. Sweeping camera passes over army continue as army marches towards castle
(6) 1:25 - Cut back to castle, viewing streets from directly above. Defenders are seen rushing to the walls. People seen rapidly building barricades
(7) 1:40 - Cut to wide angle view of armies arrayed, flags flapping in breeze
(8) 1:42 - Focus on army leader. Steps forward and swings sword to signal attack. Army takes a step forward
(9) 1:46 - Fade black to Blockland title
Maybe this plan doesn't have to be for this trailer, but I would love to see it made.