A paladin can dump constitution. I did.
Paladins need to keep an eye on both strength and charisma. They power your abilities, and it is hard to punt 1/3 of youer power choices by tanking either of these stats. You want one of those to be an 18 and the other to be at least a 14, if not a 16.
Then you need to keep a respectable wisdom for your secondary effects for some of your powers. Although a 12 or 13 for a +1 is feasible, you probably want a 14 there.
Then you have to consider your saving throws. Glass jaws really hurt in 4E, so you'll want to make sure your reflex save is getting at least a +2 from your stat. Most paladins go with dexterity for the init bonus, but paladins can also go int.
That puts us at 4 stats being filled with 18, 14, 14, 14. If we assume that we get a +2 to the 18 and to one of the other stats from race, we're looking at 16, 14, 14, 12. Under point buy, you're looking at a cost of 21 points of your 22 points right there. It is even worse for humans... That gives you 1 point to spend on constitution... (which you should do to give yourself an even number of starting hps so that your hit points will be a multiple of 4 every other level - that gives you a bit more in hit points per surge than having an odd hp total - although if you're taking toughness it may not be such a good idea...).
My human strength paladin went with:
18 str (9 pts with human +2 race)
14 chr (5 points)
14 wis (5 points)
13 dex (3 points)
10 con (0 point) (but he took toughness)
08 int (0 points)
All in all, after 8 levels of play, I wouldn't change a thing.