Well, you'd have to get all of your paladin-ing done in one shot, then go to Cleric, or vice versa, as Paladins cannot take other levels in between that I recall. However, I see Clerics as the wisdom and devotion of a deity and paladins as more of the sword and justice part. If I were a DM, I'd be okay with it. Imagine a Strength/War Cleric with levels of Paladin, that sounds so not-weird to me, I might do it. Granted, the paladin levels would be mildly unnecessary.