I was trying to find a way to roll back my char as well. i too accidently picked the wrong starting city and it's one of those things thats going to be in the back of my head for the rest of my time in FFXIV ARR unless it's fixed. i even called SE and talked to someone about rolling back my char. at the time he said it wasn't possible

But it HAS to be. they definitely have the capability to roll back your char's data. they did it in FFXI all the time when ever someone was hacked and lost items. i seriously h ope if enough people speak up they'll do something about this