By now I do not think they will let you redo starting city. At this stage it is not possible because that means you essentially have to start over and it is too complicated to reroll one character especially because that character may have joined a free company or linkshell. And if he stored his gear in the fc chest and tried to take it back out.

I do understand it is easy to make that mistake. Heck, I almost made that mistake after I finished editing my character but luckily it happened when the server was busy so I didn't complete. All I can say is try to enjoy the story or skip it up to the part you are able to go different nations and then just join the grand company of your city you liked.