It's infact a really grand idea, seeing I'm quite used to playing with elemental shamans already. Out of my current 4 accounts, 2 of them got TBC + Wotlk, while the two last only got TBC, so it's doable.

I am going to roll them on an entire new server (once I find out which one), so having a high level to support all the lower level characters would be great. One of the classes I know little to nothing about is Deathknights though, I also kept getting told that prot paladins are the way to go for PvE teams. 8|

What I had in mind was a prot paladin, priest + 3 mages, kinda a normal setup. But a deathknight + 4 shamans would probably be easier, only thing to worry about is the fact that I know nothing about deathknight tanking, but that can be learned. So for now I'll keep that setup as what I'm going to roll, thanks.