All of those types of sites are trying to either steal your Minecraft account or infect your PC with malware. Never trust any site like that. You will never be able to change your Minecraft username on a legitimate copy of Minecraft until Mojang announces that you can, and offers that service directly from their website or launcher.
Thanks sunperp, I just wanted to ask before I actually try one of these sites.
I'm sorry, but I despise this idea of changing names. Sure, I regret my name, and more so down the track because I chose it from what bullies used to call me, but honestly let's look at the pros and cons of this.
1. You can have a cool new username.
1. Server Owners can't ban you if you change your name.
2. It is morally confusing for people to distinguish you.
3. It's going to cause many problems down the track, whether system overloads at Mojang, or debates of inappropriateness.
This is why I don't condone this new idea Jeb brought to mind, it's just plain horrible and will lead to a new level of griefing.
Minecraft servers use a player's UUID to deal with player data, so if you're banned on a server usernames won't have anything to do with it.