You could certainly make that work.

Mixing up your DPS section adds some complexity to planning out your macros and so forth, but adds extra buff lines and utility options. One BIG thing that warlock gives you is wipe recovery (actually, the paladin does too somewhat). You also get options like the imp buff...also destro locks are getting replenishment which you would otherwise need to spec a mage frost to get. I'd go fire/fire/destro with those guys like this. Death Knight would be nice for Ebon Plague, anti-magic bubble, more DPS, and so forth...Paladins have a variety of helpful buffs and some good "oh shit" tools. I'd go with the DK personally, but if you're leveling the others from 1 then you might as well drag a paladin up to 60 then swap so you have it well-started and tested out.