Somebody beat me to it. Gojira is freaking killer band!
Also look at:
Amon Amarth
Arkaea
Black Label Society (not as heavy but still some good songs)
Bloodsimple
Carcass (going old school)
soulfly
Damage plan
Down
Superjoint Ritual
Epidemic (Decameron)
God Forbid
Iced Earth (Maybe, maybe not, I really like these guys)
Isis (You might not like these guys, they are almost along the lines of Opeth)
Katatonia
Killswitch Engage
Kittie (I know you don't like female singers but they are just a tad different)
Otep (see kittie)
Strapping Young Lad
Testament (See Demonic!!)
Throwdown
Spineshank
Soil
Sepultura
Godflesh
Paradise Lost (Depends on which album you hear, older stuff tends to be a little heavier)
Obituary
Mushroomhead
Morbid Angel (Listen to the album Covenant then move on to the others)
Cannibal Corpse
Six Feet Under
Those are the ones off the top of my head.
You already mentioned Fear Factory, they are my favorite band!