Q276 Would a Paladin with a full caster level (same spell progression), spontaneous casting from the core paladin spell list, and cha-based casting be Tier 3 (or maybe even 2)? Or still Tier 4?
A276 Tier 3, if a bit low. He's still got a rubbish spell list, and still has a bad bit of MAD (Str, Con, Cha), though it's alleviated a bit - if you made it Wis-based instead, you'd open up killing some MAD for Paladin Archers (Zen Archery, etc). Changing everything to run off Wis (including Divine Grace, Lay on Hands, Smite) and changing Smite (to something non-Alignment based, possibly) would make it a more solid Tier 3 class. It'd have a couple of niches worth filling (Wis-based Archery with some support spells, capability to dish out some heavy damage a couple of times per day, etc) and would be okay at those niches, if not seriously competent.
For Tier 2, you'd basically have to make him the Spontaneous Cleric UA suggests. Note, this is opinion, and probably deserves its own thread for discussion with people more competent at gauging tiers than me.