Isn't it a GFDL violation to change someone's username (and thus their entries in the history section) without their permission?
No. It would probably be wise to put a note on the user page saying that this user was formally known as X, but that should be all that is required.
The current rename function doesn't move everything (eg. deleted edits), so this would need to be fixed, but I imagine that is a tiny job in comparison to the rest.