Flickr.com has over 5 million users in it's system.  You have always been able to have a free 200 image account there and always there has been a free inbuilt option to change displayed user name any time you like. The changes are tracked and displayed on user profiles, thus a user cannot hide the fact that they have changed their username, but it is free. 

Username changes should be free here as well. Disappointing Renderosity.