Here are all the champions:
Alistar, Amumu, Anivia, Annie, Ashe, Cho'Gath, Evelyn, Fiddlesticks, Jax, Judicator, Karthus, Kassadin, Master Yi, Morgana, Nunu, Rammus, Ryze, Singed, Sion, Sivir, Soraka, Teemo, Tristana, Tryndamere, Twisted Fate, Twitch, Veigar, Warwick, Zilean.
Present your list of champions that deserve a solo, in order, starting with the most deserving.
My criteria are threefold: Lane dominance (ability to threaten the enemy through leveling faster than them), lane durability (ability to hold your own 1v2), and lategame dominance (the boost provided by soloing is worth it to your team lategame, when you provide some significant benefit due to your increased levels and farm).
Based on that:
1: Karthus. A+ C A. He can easily get first blood, but the only defense he has is his wall of pain. Lategame fed Karthus is a monster.
2: Anivia. A B+ B+. With stellar harassment and great durability, makes a fine solo choice.
3: Fiddlesticks. B A A-. While not generally a first blooder, it is difficult to kill a solo Fiddlesticks earlygame. An early crowstorm is where he really shines.
4: Zilean. B B- A+. Zilean, as one of the best harassers, is best paired vs the enemy carries to keep them in line earlygame. IMO he is the best support in the game, and very level dependent. The boost from the early solo will not be amiss lategame as he supports your team to high heaven.
5: Twitch. A A- B-. A good Twitch is fantastic at shutting a lane down, but lategame his potential is limited vs a good team.
Note that I didn't include typical carry-solos like Ashe or Tristana because I feel that they simply farm the earlygame while not impacting the enemy lane very much. I feel there are better uses for a solo. However, if through a jungler you grab 2 solos, giving them a solo as well is a fine choice.
Other picks that are decent at soloing might be Jax, Singed, Yi, Sion, Sivir, Tryndamere, Twisted Fate, Veigar. They just aren't as high on my list.