Skill checks? I did offer some others, but I would need to look into my old books again. Wasn't there rules for specific, difficult and extended skill checks in Unearthed Arcana?
What about allowing torture/intimidation/corruption to do damage? When 0 hps reached (if the paladin doesn't die) he/she might be twisted. Though this sounds too simplistic to me, it might suit the game you are playing. (Just like swinging from chandeliers might be made easier in a swashbuckling campaign).
This reminds me - in our home camapign world we actually had rules for Corruption and some opposite for good. (I think, initially based on some corruption rules from BVD). It was a scale you could move up and down (and you got powers, abilities based on your devotion to good or evil). We also had an Honor one. These replaced Alignment in our home world, but that world was a physical representation of these forces too. An evil god is imprisoned within the world and struggles to release its corruption, whilst the world is a 'Nature' deity itself with the power to contain such a being, so there was also a 'maintain nature' feel to the rules as well as ultimate goodness on the other side of the coin.