The Parchment - these were the clues:
Clue 1:
A line in this song's lyrics alludes to a story from the Bible.
Cross to bear
Clue 2:
Thematically, the song associates with other Maiden songs such as Genghis Khan, Innocent Exile and Alexander the Great.
The song is (probably) about Mithridates The Great, who like Alex and Genghis became a ruler who conquered vast areas. He spent time in exile, hiding from his mother, before he could return to seize power.
Clue 3:
The name of both a Kiss song and also the name of a Kiss album it was released on, appear in the lyrics.
Unholy. Revenge.
Clue 4:
In the lyrics there are also song titles by Guns'n Roses, Judas Priest, Ozzy Osbourne and Deep Purple.
Patience. Tyrant. Fire in the Sky. Burn.
They fire off many shots: For the Greater Good of God, Lord of Light, The Man Who Would Be King, Twilight Zone, Stratego, Mother Russia, Senjutsu, Revelations