Putting the ‘ideal’ aside for a moment…
If they have a set of other custom fields already that are searchable then creating a new ‘Location’ one would probably be the smoothest option. 
If you can migrate the existing values from the inbuilt Location field to this new Location custom field, and then ‘retire’ the default one by hiding the input box in the profile and the display in profiles and user cards then that should do it?