Can you try this? It won't break anything and you can drop it if you want. As always, do a backup first.
alter table yourtable add my_id int(11) primary key auto_increment first;
What *should* happen is it will place a new column at the far left of the field list (left, by usage of "first") and add the id's in the order they were entered, giving you that field to order by. If it errors it means you already have a primary key, even if it's not an auto_increment.
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.