I am currently leveling my first dualboxing team ever and i started out with a draenei shaman/paladin. They reached Level 47 last night (yeah, no big deal, but I got exams at the university right now).

My primary motive was the high survivability and the damage dealer / healer combo. I agree with Xiven, that it is a little hard to get positioning right to be able to melee with both chars, but it just takes a little practice.
Around Level 40 I respecced the Paladin from pure Holy to 17 points Retribution and the rest back to Holy. Currently I am thinking about ditching Retribution and specing towards Protection for Blessing of Kings.

Pros:
  • you can duo "everything" (normal Mobs up to +5 Levels compared to yours, most Elites up to +2 (Tethis, Bangalash, Bhag'Thera - you name it) and (using this a lot) adds)
  • got a nasty 3-5 man patrol? Chain Lightning, Magma Totem, Lightning Shield, Retribution Aura and Consecration will take care of it
  • saved 81g by getting the Riding 75 skill for free (bought an elekk though because draenei on a warhorse is not easy on the eyes)
  • Blessings (!!!)
  • Reincarnation + Divine Intervention + 2 chars with ressurrection

Cons:
  • can't use Ghost Wolf
  • PvP: when the shaman (computer -> better hardware) dies, the paladin (laptop -> a little older) is dead meat as well -> this is mainly due to the synergy bug, that makes your camera spin out of control when trying to use mouselook (tried the custom version, froze up for me)
  • Horde seems to dislike draenei shamans: up to now I had half a dozen ?? players get of their mounts to just kill the shaman and then move on

Hint:
When trying to decide for a class, think about their playstyles. For example: I thought about teaming my shaman with a mage. Imo it wouldn't work that well because of their different playstyle towards mobs.
Mage: nuking -> drinking/eating -> rinse and repeat; multipulls/adds: frost nova -> run -> AoE
Shaman: Lightning Shield -> Stormstrike -> 1-2 totems -> melee to death -> rinse and repeat; multipulls/adds: stoneskin / magma / healing stream -> try to keep aggro of all mobs/ heal -> melee them to death
Of course a casting shaman would have maybe worked better with a mage (summon water/food), but since I started this game, I wanted to be "a hurricane", so Elemental was not an option.
But I guess, you get the idea: both classes should either share or complement their playstyle and unless you are a 300 APM korean RTS gamer, there is only so much you can do per second (also because of latency, global cooldown, server response time and hardware).

Other "good combinations" that come to my mind would be:
  • 2x the same caster or 2x hunter -> this is a nobrainer - 2 frostmages, 2 affliction/demo locks, 2 shadow priests; fire mage + destruction warlock would be interesting; as hunters it is up to you whether you want 2 beastmasters, two marksmans or one of each; each combination has its perks
  • mage + priest/warlock + priest -> again: shadow priests with an occasional HoT / Greater Heal
  • melee + priest -> again, a nobrainer - the healer should keep his debuffs up (SW:P) and wand the target to death
  • melee + marksman hunter -> be sure to just use autoshot mostly and keep feign death ready
  • beast master + mage/shadow priest/warlock -> keep only the "tank abilities" (growl / screech) + maybe claw active; the damage will be done by the hunter and the caster; as a warlock, use an imp

Combinations I would stay away from:
  • 2 rogues/2 warriors -> there is almost nothing to be gained and you will lose a lot of time to false positioning and healing
  • 2 shamans/2 paladins -> although the healing is there, this team still lacks diversity and killspeed


Keep in mind, that all of these suggestions are made for the "plain old two-boxer" or beginner like me.
I also still not sure about druids. I guess a druid would go nicely with a mage/warlock (innervate + moonkin aura), a hunter/priest (feral spec) and a melee (moonkin or feral).

Oh, to answer it in advance: I did not choose a hunter, rogue, warlock, priest or warrior to team up with my shaman because I already have those at 60. They will, however, be accompanied by the Level 70 Paladin one day.