Non-AC defenses were around in 3E's Unearthed Arcana, where they had a few different ways of rolling for hits and saves (players roll all dice, attacker rolls all dice, etc.).
Feats: Tangential, but Hercules had a few.
Obviously the Paladin has been around long before the 4.0 D&D class. That's not interesting nor informative. Has the Paladin been around as a CLASS before 4.0 D&D, which was really the question? The "concept": yes. The class? Only in previous editions. Which edition was the first to have a Paladin? I dunno. There is answer, however. t.