Avenging paladins should probably have their second best stat as Charisma anyway (as suggested in PHB). I guess I don't see this giant problem with picking a charisma power here and there for an Avenging Paladin. Some of the Charisma powers feel more "avenging" than the strength powers anyway.
Imagining the stat layout for an Avenging Paladin, most non-human races would have 18/16 or 16/16 in Strength and Charisma, and a 14 in Wisdom.
Dragonborn S18, C13, D10, I8, W14, Ch16
Dwarf S16, C14, D10, I8, W14, Ch16
Eladrin - forget it.
Elf S16, C12, D12, I8, W14, Ch16
Half-elf S16, C15, D10, I8, W14, Ch16
Halfling S16, C12, D13, I8, W14, Ch16
Human S18, C13, D10, I8, W14, Ch14
Tiefling S16, C13, D10, I10, W14, Ch16
Looking at the 9th level daily powers, two of them are close bursts, so you are still expected to use them while engaging enemies. Also both powers attack Will which is typically a low defense. Ranged daily paladin powers in general are actually less to my liking, than the lack of a 9th level strength based power.
I have to admit, the avenging paladin is my least favorite build from the PHB, but that's more a matter of my dislike of their powers overall.