Whatever system is hidden in the background to mix different faces and body types I think could be used for character creation. You could still keep the special hairstyles and facial hair options as vanity items to purchase but all the basics that’s used in the random character generator should make for a pretty diverse character creator.
I think for those who don’t want to start over to create a character could probably just do it in the vanity chest or something. Perhaps there is a magical item that allows one to change their appearance for a price.