I disagree that this is the only solution. The OP comes very close to discovering an alternative one: don't allow users the power to select their own arbitrary username.
When a user makes an account on your site (and if your site actually needs publicly-displayed usernames in the first place), give them the option of, say, ten usernames generated by the site itself; these don't need to be numeric codes like WeChat does, they can be pronounceable phrases in the same manner that Gfycat generates URLs. Everyone will end up with names like "questionable wet aplomado falcon", "each unlawful harlequin bug", "icy inferior iceland gull", which honestly isn't any worse than the average name I encounter on Reddit or elsewhere.
The biggest downside(?) of this approach is that it makes it harder for someone to build their personal brand, but the older I get the more I think it's a bad idea to use a consistent nickname across different websites.