Professions take about as much time with either approach.

You can level them as you're leveling your toons.
Or you can wait until 60th or 80th, and then level them.

The higher levels can pick flowers or skin with relative impunity.
And the faster mount lets you move from one to the next easily.
Not slowing down to pick flowers, mine ore, skin mobs etc speeds up leveling.
But this means you have to go back to the zones even after leveling there already.



Some of the class quests are definitely worth doing immediately.
Others can wait, as your team is strong together even without a totem or a pet.
It is preference really.
When I was leveling 5x dps toons, I'd frequently only bother to train at multiples of 10's.
Of course the team had RAF for faster leveling.
But still they had no problem doing quests for level x9 with spells from level x0.


Collection quests will pretty much always suck if you look at them as collections.
When you view them as short-term grind sessions, with a reward at the end, they're a least tolerable.
Not the preferred method to level on, but not as horrendous either.
When I'm in a grinding mood, I'll definitely have a dvd going for a bit of a distraction.

The only collections you "have to do", are those that open up a quest chain or daily really.
Or if they end up with a very nice reward, which you'll use for a while.
Until you're in Northrend, and are opening dailies, every collection is optional.
It will be hard to level without collections in Northrend, but through Vanilla/BC content, you don't need to do any.

Even in Northrend, you can avoid the more painful collections.
If you do, you'll likely need to hit every zone to level.
And maybe either instance some or battleground some for extra experience along the way.
Definitely try all of the collections, you'll need to do some of them.
Occasionally they're easier then you think.
Especially if every toon can loot the corpse, which is true for some collections anyway.


As far as leveling goes, irregardless of your final spec, I'd spec each toon to DPS.
Once the Paladin has Blessing of Sanctuary and Holy Shield, prot is a decent leveling spec.
Until then, you'll do a lot more damage as Retribution.
All your other toons seem to be DPS spec, which will help you level faster.