There's always worn haste items and clicky haste like eyepatch of plunder to help you out. I doubt a lack of spell haste would hinder your progress much.
2k for CoCW was posted lately in alliance, thats 36% and cheap! I wish that was available when I was leveling! It was 10k for FBSS then
. Plunder eyepatch (or Pally self haste which is 30%) will be regularly used
Don't ignore the pally/shaman combo. A troll shaman that worships the right god can get a snare clicky necklace with unlimited charges. Knight/Druid can be a fun combo as well. No slow, but you have evac; if it gets ugly. Plus, with a pally, you have stackable hp buffs, DS, solid dps from Druid, and good healing.
Personally I did a Warrior/Cleric duo box (added wizard much later on after I hit 65 on both W/C, yes, I still don't box a slower!). I actually only really remember using my cleric's snare neck when I was leveling on HG's or when I did "sticky" named in dungeons. The Cleric "shines" more in that duo than most other duos (pacify vs FD pull, etc)
I've always considered doing a Paladin though, if I ever leveled up a duo again. They can pacify a surprising percentage of things pre PoP at lvl 51 (ex: I'm guessing they can pacify 80-90% of ssra, for example)