well,
I have not built a shaman paladin team yet.
But for mine I am going to continue with the versatility theme.

Priest - Engineering/Enchanting (currently Enchanting/Tailoring)
Druid - Engineering/Alchemy
Warrior - Engineering/Herbalism
Mage - Engineering/Inscription
Paladin - Engineering/Jewel Crafting

Not in group
Rogue - Engineering/Mining (already there)
Shaman - Engineering/Skinning

This will give me all of the "re-sale" professions and the gathering I need for it.
And of course I LOVE engineering. :)