OP didn't list professions, but Mercurial Alchemist Stone and Sapphire Owl are obvious if they're available.
Other than that, from non-raid sources (ordered loosely in order of throughput benefit): Winged Talisman (HoL-H) - Mp5 with a SP proc Soul Preserver (CoS:S-H) - SP with a mana saving proc Forge Ember (HoS-H) - Crit with a SP proc Tears of the Vanquished (ToC-Normal) - Int with a mana return proc Darkmoon Card: Illusion ($$$ from Darkmoon Faire) - SP with mana return use effect Je'Tze's Bell ($$$ from the AH) - SP with a Mp5 proc Darkmoon Card: Greatness ($$$ from Darkmoon Faire) - Int with an Int proc Egg of Mortal Essence (Emblems) - SP with a haste proc
For general purpose use, I carry the two with Int equip effects (DMC:G and Tears).
I don't really believe the Egg is that high - I think it would be more useful in the real world with a constant level of haste instead of a huge short-time proc, but 40 random emblems are easy to scrape up these days. DMC:G is under 5k on my server and dropping slowly but surely in price. You might need to run non-heroic ToC quite a few times to get Tears, but on my server at least, there are still plenty of trinket pugs, and it procs off literally anything like the Shattered Sun necklace used to.
Go for +Int trinkets if you can, ToC 5 man one for sure. I personally stack Pandora's plea and the +Int Greatness Trinket.
If you have to use one of the entry level +SP trinkets then go with the Egg. The random proc +haste buff is better than any alternative (HoT one from naxx for example. Especially if you are below 300 haste, a very nice trinket for you.
If I was gearing up a new paladin and I was not a JC I would get the TOC trinket and farm badges for the Egg.