Anything off Chimaira's "Chimaira" album. It rocks. Unlike some metal bands the lyrics are hearable. The lyrics are direct, you won't have to think too long about what they mean.
http://www.chimaira.com/chimaira/ Ecard with the entire new album, in less than optimal quality though.
Surgestions for the individual songs:
Inside the Horror: Akira or Project Arms. Anything with a psychological theme would do aswell.
Save Ourselves: Title says it all. This is a quite varied song so there's plenty of good timing to be done.
Left for Dead: Berserk or Gun Grave. Again the title sets the theme pretty well. It's about betrayed trust and, well, being left for dead.
Anything off Devildriver's "The Fury of Our Makers Hand". Again a great album. The lyrics here can be heard but not as easily as with Chimaira.
http://flashenhanced.com/devildriver/ecard/# The Ecard of this album. It only has 3 songs though.
End of The Line: This is probably the song on this album i see the biggest potential in, AMV wise. Fairly large melodical parts and a killer chorus. It's on the Ecard. Anything about cheating fate or denying your nature would be a good mix with this song.
Opeth's "Ghost Reveries" is a masterpiece. Anyone looking for something different within the genre of metal, look here. i ahvn't got anything for the individual songs though.
http://www.roadrunnerrecords.co.uk/opeth/ecard.htm an Ecard again, only two songs though.
Gojira is also an underrepresented band in my oppinion.
Their site: http://www.Gojira-music.com you should be able to find a good deal of their music there. Only one song from their newest album though.
I'll stop linking bands for now and hope your google-fu can do the trick.
Illdisposed: Groovy Death metal. It's like typical american (ie. not In Flames) death metal but with a lot less hostility, it's just as heavy and very groovy.
Raunchy: Cybermetal mixed with pop and Thrash. I'm a major fan of this band so anything i'd say would be blind appraisal
.Gorefest: varied death metal. Their songs usual have allot of different passages, not just the same thing played over and over.
Lamb of God: Listen one of their songs (off one of their two newest albums preferably) through a few times and you'll be hooked (ok maybe not if you don't listen to metal usually
). They're all very good musicians and the music showes. Again a band that tends to make varied songs.