That's a perfectly reasonable way to do it. Any suggestions for how the penalty would work?
On the topic of half-celestials and ECL: My general rule of thumb is that ECL characters with no HD (drow, half-celestials, half-dragons, etc.) shouldn't enter the campaign until the average party level equals ECL x2. Thus, I'd not allow a half-celestial character until the APL equals 8. IMHO, a 4th-level half-celestial fighter is perfectly survivable in a party of 8th-level characters; a 1st-level HC fighter is not survivable in a 5th-level party.
Mordeth: At ECL +2, you absolutely, positively should take an HC paladin, even at 1st level. If you get wings (ask your DM how he determines this), it's even more worth it.
Take your HC human paladin and arrange scores like this (HC bonuses in parens):
STR 14 (+4)
DEX 12 (+2)
CON 14 (+4)
INT 8 (+2)
WIS 10 (+4)
CHA 16 (+4)
Total scores:
Str 18, Dex 14, Con 18, Int 10, Wis 14, Cha 20
Starting feats: Power Attack, Flyby Attack (if wings) or Dodge (if wingless)
Init: +2 Dex
AC: 17 (+4 chain shirt, +1 natural, +2 Dex bonus)
Speed: 30 ft., 75% chance of fly 60 ft. (good)
HP: 14
Attacks: By weapon +5 melee; by weapon +3 missile
Damage: By weapon +4 Str
Special Attacks: Spell-like abilities
Special Qualities: Low-light vision, immune to acid, cold, disease, electricity, +4 Fortitude save bonus vs. poison
Saves: Fort +11, Ref +7, Will +7
Compare this character with a 3rd-level human paladin. The human gets one more feat (3rd character level) and 2(d10+Con) additional hit points. He loses out on damage, saves, and ability to fly, gains none of the HC spell-like abilities (which are REALLY useful at low levels), and is even-on in attacks due to the HC's higher Strength and Dexterity, which compensate for the lower BAB.
Definitely worthwhile to take the HC over the human.