Paul Regret is a character of the original bang! set and he is quite balanced with the other 15 characters, playing the original deck (80 cards). In general I do not like too much to play with 3 lifes and 3 cards but it's just my preference.
Actually, once Dodge City came out, a correct balance would be probably "3,5" life points (this is impossible, you know); but take care, if you simply compare characters in an hypotetical 'final duel' you get different results than what you get from a full game, ex. with 7 players.
Playing WWS expansion it wouldn't be a crime to play him to 4 life points, but it's not enough to do an official and definitive upgrade, IMHO