You could probably get a prosthetic and/or active device of some sort that would eventually teach you a consistent new way of walking.
People also claim to have learned new ways of walking through posture exercise like Alexander Technique or Irene Dowd's work, although I don't know if those are big enough changes to be visibly different.