For example, reserve the usernames 'deleted-xxxx' where x is a number. Then when someone wants their history obliterated, loop over every thread they have commented in. For each thread, choose a random number deleted-xxxx and assign that username to every comment of theirs in that thread.
Thus comments in the thread remain linked with one another, other deleted users in the thread remain distinct, and comments in one thread aren't linkable to a user's comments in another thread (perhaps lamentable, but required for unlinking spilled personal info in the general case)
(I chose random numbers rather than incrementing so that one can't start making inferences about users based on deletion order)