by "level solo" i'll take it as : solo elite quest mob(aka. 2~3 group quest) plus the long grind with little down time.
i would say
demo warlock, hunters, affliction lock,
aoe, one by one, solo group quest, little or no downtime, all good
you only stop when either you ran out of quest mob, or your eyes are tired.
next would be
feral druid,
one by one, solo elite, no downtime.
frost/arcane mage, Boomkin(balance druid),
master of aoes, but need to eat or drink.
i'm not sure of, but they maybe good but with some downtime:
enhance shammy, paladins, rogue(maybe)
I've got one of each class at level 80 (2 85s atm) and I have to say, prot paladins are pretty easy to level - can't recall if AoE grinding is still feasible but I got from 1-70 in 15 hours played thanks to AoE grinding back in the day. Just levelled a shaman, priest and warrior to 80 shortly before Cataclysm was released and of the lot, I found that the warrior was the easiest to level imo. Spec prot and then farm instances. Got from 1-80 in about a week and a half thanks to instant tank queues. If instance running isn't your preferred style, I recommend trying out an enhancement shaman. Virtually no downtime (unless you decide to pull 20 mobs at one go), easily solo elites and good survivability. If you enjoy pet classes, warlocks are definitely pretty awesome. Affliction locks have no downtime - spam dots and fear (I used to run around, dot 10-15 mobs and then pop Howl of Terror). Personally, I reckon the hunter was the most boring class to level. Everything seemed far too easy and I was dozing off half the time in instances.