Okay, I listened to Einherjermarsjen.
I think you want Bal-Sagoth. They are basically a whole band built on this sort of stuff. Tracks of particular interest might be 'And Atlantis Falls', 'Behold! The Armies of War Descend Screaming From the Heavens', 'The Dark Liege of Chaos is Unleashed at the Ensorcelled Shrine of A'Zura-Kai', 'Naked Steel (A Warriors Saga)'...actually, all of it. Most of their songs have that sort of stuff in there, mixed in with nice whacks of keyboard excess and symphonic black metal.
Other marching rhythm based metal tracks to check out off the top of my head:
Amon Amarth - Siegreicher Marsch
Forefather - Proud to be Proud
Manowar - Funeral March
Nazgul - Caelum Obscuratur
Running Wild - March of the Final Battle (End of All Evil)
Skyclad - Jeopardy (The marching is used satyrically, but still)
Turisas - Vicoriae And Triumphi Dominus
I particularly recommend the Forefather. In fact that whole album, 'Ours is the Kingdom', would probably be right up an Einherjer fans street. It's one of my favourite 'viking' metal albums.