Regeneration (no weakness) + immunity to nonlethal = immunity to damage, PERIOD.
Now, how would you fluff the immunity? As the character being simply invulnerable, or, considering that the immunity is based on regeneration, make it so that the character has super extreme regeneration that heals him so fast that he barely even notices being damaged?