I also vote for mixed teams. They give so much flexibility and their buffs work together. Like Alge, I tried doing instances with mixed teams. I personally found it a pain in the ass because they have so few abilities at lower levels. For questing all you need is 1-2 dps spells and 1-2 heal spells so their lack of abilities is not important.

With your existing comp all you'd need to get to 60 through questing is:
Charge/heroic strike
Smite
Shadow bolt or immolate
Fireball
Arcane & autoshot

Since you don't have RAF and you're finding the leveling not to your liking, why not use the paladin to power level them in instances. You can switch out the warrior at 55/56 for a DK if you want. A priest can handle the lack of a shield.