Retroactive auto-numbering is currently not possible.
In Specify 6, you can use batch editing to assign numbers to existing locality records based on the field you want to edit.
Alternatively, if you are familiar with SQL, you can also achieve this as well by running commands on the database.
Do either of these approaches seem feasible to you?