You can even blend it in the world of skyrim:
Go to a major hold => The jarl's House => Talk to a steward => "I'd like to change my name" => Steward: "of course Sir. But you do know that it requires a large sum of gold to get it done? We need to get word around Skyrim and need to change some papers, jada jada ..."
I got this idea because we can change our appearance and abilities already with 2 DLC's. So I thought it would be fitting to do this as well for free or in a DLC.
Yes I know PC users (such as myself) can use console command but why not let everyone else join it as well?