You got Demons and Wizards and Blind Guardian on there, so I'll assume you just forgot the mention Iced Earth.
Besides them, I recently came upon Masterplan, a band that very few people ever seem to mention. Another band suffering the same problem would be Edguy.
Judging from your list you may or may not like Samael. Their old works are death metal (with appropriate production quality it seems) and their more recent works are somewhat progressive/industrial, like the one I linked to. Their most recent album harks back to their roots (which is a shame if you ask me). They have a lot of esoteric influences though, so that may be a turnoff if you're keen on the lyrics and really down-to-earth.
There's also Amorphis. They tend to get repetitive after a while but they're good for a fix now and then.
On the topic of non-metal bands, I'd first like to suggest Abney Park and Vernian Process, two indie steampunk bands.
Besides them, I'm also pretty partial towards some 80's bands, primarely Duran Duran (for the record, I have absolutely no clue about what's happening in that video) and the Dire Straits. Oh and I'm forgetting Toto and Bon Jovi here.
You know what, I love you man.
Masterplan, Edguy, Amorphis, Bon Jovi. I've also heard a bit of Vernian Process and think they are pretty cool.
For my suggestions;
For something humorous/insane try
Lordi. If you like Rammstein you could check out the band that inspired them,
Oomph! (
2). Or if you want something more mellow
Porcupine Tree (
2) is pretty nice. The opposite of that would be
Strapping Young Lad. If you enjoy Powerglove maybe
The Protomen might be something you would like.
Trans-Siberian Orchestra hits that classical spot well.
Blue Oyster Cult (
2) should already be known to a good amount of people, but are great.
Scorpions (
2) to represent old rock. A good folk band is
Heidevolk (
2) but are not for everyone.
Flogging Molly (
especially this) are my favorite punk band, and finally
Insomnium, which are a melodic death metal band with poetic lyrics.