If you're not allowed to alter the existing table, you could pull the data into a temp table. It's a bit more brute force and may not work well if you're doing it a lot on a huge table.
Have the temp table be the exact same structure as the existing table plus an auto_increment field. Select the records into the temp table. Then you should be able to use rocknbil's suggested solution on the temp table.