Consulta el manual de
Alter table para agregar la columna
despues con un ciclo actualiza los registros para crear un consecutivo
cuando termine de actualizar borra la llave primaria que tenias y declara tu campo nuevo como llave y cambialo a autoincrement
si no sigues los pasos, lo mas seguro es que te maque errores con las primary key y/o key duplicadas...
Saludo