Is there a way to let the users edit their usernames?
no.
I think you summarized nicely why this should not be easily possible, since a change of user name will change the URLs of pages in the site something that only an admin should be able to do.
Of course you can write a plugin that will do that if you truly want it but the better solution is to either change the code of the plugins that you are using to produce a saner names, or let the users select a name when registering (if you think the default is not good why do you force them to make a second step to change it when that step could have done with the registration).
In any case, as long as you do not point to the users author pages the url issue is purely theoretical.