So leveling fast is 99% about travel speed. That puts hunters, druids, shaman, and mages above all else. Warlocks get an honorable mention due to their ability to mass pull an entire area.

To cut straight to the chase, the answer is either
If you have a pre-planned route then the answer is easily hunter/hunter.
If you dont have a full planned route, then mage/mage obviously to port.
and if max level asap is your goal then there isnt any other options.

If leveling to max is your priority, then do not worry about earning or saving gold or cost of drinks and ammo. Do not gather or do any professions. You will make 100x more gold in the first 2 hours at level 70 than your entire leveling process, and gathering/professions are far easier to advance at max level than while leveling, plus on a fresh server every node in the starter area will be swarmed. When you hit 70, a lot of the wotlk quests and likely an entire zone or two will not be completed, and those quests when you are max level give gold instead of exp. Also you will need the reputation, so it's easy gold and you can also farm elementals in Wintergrasp for serious money. So dont waste any time at all making gold while leveling.

The only other class worth pairing with mage is hunter, but you dont get aspect of the pack until 40 so it's definitely not worth it unless you want two different classes for end game.

Druid/druid is a good alternative as balance but it's not as good as hunter/hunter. As feral you lose a lot of time getting into melee range for everything though this is ferals first powerful era. It can be better than hunter on an active pvp server though, so consider that, but also consider that if you're leveling on a new server then you'll be higher level than any pvper and those that are your level are just worried about their own leveling.

Shaman/Shaman really hit their stride at lvl 30 with recall, very underrated speedrunning class because of slower kill times, but that is greatly reduced when dualboxing and they can take down elites pretty easy similar to hunters.

if you got this far then the best tip i could give you is to buy Joanna's leveling guide and practice it at least one time during beta or on TBC before official release. It's really important to outpace the mob of starting players if you're questing.