So here we go...
Clue 1: In the lyrics to this song, you can find the names of a song from these bands: Gojira, W.A.S.P and Misfits.
Clue 2: Genghis Khan could lead you to this song.
Clue 3:
Rock and Roll Roulette
Clue 4:
The writing credits to the song are not unique in the Maiden catalogue, but are unique on this album.
Clue 5:
When it comes to lyrics, both The Mercenary and 2 Minutes to Midnight offer strong hints to the song you're looking for.
Slaves to the power of the wrong guess: Powerslave, Hell on Earth, Senjutsu, Alexander the Great, Out of the Silent Planet, Nomad, Innocent Exile, The Parchment, Hooks in You, Public Enema No. One, New Frontier