AFAIK, you can't conditionally add a constraint on a database column. You could, however, add unique constraint across two columns (though a boolean is_deleted might not be a good candidate for this case).
Add unique constraint on fields(username, deleted) Change field type for 'deleted' to INTEGER.
During delete operation (it can be done in trigger, or in part of code where you need actually delete user) copy value of id field to deleted field.
This approach allow you:
keep unique names for active users (deleted = 0)
allow delete users with same username several times
Field 'Deleted' can't have only 2 value because the following scenario will not work:
you create user 'Sam'
User Sam is deleted
You create new user witn userName 'Sam'
You try delete user with userName 'Sam' - fail. You already have record userName = 'Sam' and deleted = '1'
=============
and i think the best practice is defining the softdelete and keep deleted time, and create a unique index on this two fields: code and deleted_at