It will be hard to find, but it’s still such a lovely, angry song.
Leslie Fish has a sung version of Rudyard Kipling’s Birds of Prey March. A hugely bitter, angry poem, and song. But her tune is a very powerful, cheerful marching song. It really was great fun to run to, back while I was pretending to care about my health.
My dirty little secret: I’ve got the Music in Me by Kiki Dee
Get some System of a Down songs from their first 2 CDs (self titled and Toxicity). Throw in some Avenged Sevenfold too.
Dorky song, but I think the Proclaimers’ 500 miles would be good.
Here is my “Fierce” workout playlist; not all of these songs are uptempo, but they all get my bloood moving in one way or another:
Limiter - Machines Of Loving Grace
Headhunter V1.0 - Front 242
A Small Victory - Faith No More
Dragula - Rob Zombie
Stigmata - Ministry
Hammering In My Head - Garbage
Them Bones - Alice In Chains
Breathe - Prodigy
Firestarter - Prodigy
Dumb - Garbage
Let Me Drown - Soundgarden
One Man Army - Our Lady Peace
Gentlemen - The Afghan Whigs
Cheap - Machines Of Loving Grace
Lilith/Eve - Machines Of Loving Grace
Smack My B***h Up - Prodigy
Midlife Crisis - Faith No More
Butterfly Wings - Machines Of Loving Grace
Perfect Tan (Bikini Atoll) - Machines Of Loving Grace
The Chemicals Between Us - Bush
Anything but This-Coal Chamber
Prophecy-Soulfly
Snap-Slipknot
“Do Your Thing” Basement Jaxx
Lukin by Pearl Jam
Police Truck by The Dead Kennedys
Birth Ritual by Soundgarden
Eye of the Tiger and the theme from Rocky seem like obvious choices.
**Train kept a Rollin’ ** by Aerosmith
**Otherside ** by Red Hot Chili Peppers
In The Gadda Davida will provide a comfortable rhythm.
For the heavier need -
Living Dead Girl - Rob Zombie
Symphony of Destruction - Megadeth
Sad but True - Metallica
Kickstart My Heart - Motley Crue
Crazy Train - Ozzy
Du Hast - Rammstein
Corny - but I like it
Eye of the the Tiger - Remix - I think it’s by Dr. Dre?
Mortal Kombat theme - Something about the “Test Your Might…”
Hotride - The Prodigy
I clicked on this thread to add “Just One Fix” by **Ministry ** off the same CD, Psalm 69. As I have stated in a previous thread on the SDMB, this is the most relentless song I can think of - and that’s a very good thing.
One Week by Barenakedladies?
Flight of the Bumblebee? (IIRC that at some other fast tempo songs are on the Kill Bill vol 1 soundtrack - though there are definitely slow tempo ones as well)
Brian
Based on the OP’s original song selection, some tunes I tote along that you might dig include (other than “Jesus Built My Hotrod”):
“Ride The Lightning” and “Whiplash” by Metallica.
“I’m So Bad Baby I Don’t Care” by Motorhead.
“All In The Name Of…” by Motley Crue.
Not too many specific suggestions, but a genre you might want to try: Industrial/EBM (EBM is Electronic Body Music). A lot of it is very fast-paced and might suit what you’re looking for quite well. Good examples include:
“Remove/Replace” by Icon of Coil
“Reducer,” “Recovery,” and “Vacant Bodies” by Cruciform Injection
“Date of Expiration” by Funker Vogt
Numerous things by Assemblage 23 (too many to mention)
I find this stuff to be great exercise music–pounding beat, fast pace, full of energy.
If you’re going by the video, can I nominate Call On Me? 
I Missed the Bus , by Skankin’ Pickle.