Warrior/Shaman is basically as good as Monk/Shaman. In other words it's very very good
[You must be logged in to view images. Log in or Register.] Just keep the warrior berserk for extra dps.
The other healer options (including paladin) are decent.
You can try other combos with classes that can fear or aggro kite (but a rogue is better duo for fear or aggro kite classes).
You can also duo with a monk, let the monk tank until low health then feign, then you tank, then you both bandage up.
Really though nothing is even close to Shaman for your duo partner.