Some websites that have account for users , give an option to change their username. It appears to be a trivial task. I have implemented this functionality in 2 of my projects . The functionality i used was to ask a LOGGED IN user for the new username and would ask him to reenter the password. This is a very simple approach and works well for small applications that do not have very much functionality in terms of databases.
     
     I recently changed my username on Github and was wondering what procedure they followed. I think it is highly improbable that they use the usernames that we see internally in databases too. What I mean is that suppose Mr. XYZ does a commit in his repo in Gihub (XYZ is the username), so in their database that stores the history of commits, XYZ is not stored, rather a hash( for more security) or a simple unique number is stored. Their would be a user table where each such number or hash uniquely determines a user and does not change anytime, no matter how many times the user changes his username. Whenever some information is displayed that should identify "who ? ", they would simply fetch the username associated with the unique number or hash (of course they could store this number in a session variable to avoid querying the same thing). This gives the advantage is that you don't have to traverse through your entire database and substitute the old username with the new one. You simply change the username in the user table and the unique identifier(the hash or the number) remains the same. It would greatly bring down computations required for trivial task like this.