Открих, че това работи перфектно и доста бързо, така че ето го:
ALTER TABLE tablename DROP id
ALTER TABLE tablename ADD id INT NOT NULL AUTO_INCREMENT FIRST, ADD PRIMARY KEY (id), AUTO_INCREMENT=1
Знам, че това не е правилният подход, но за моята конкретна ситуация точно това беше необходимо. В таблицата, която използвах, няма нищо, което да се отнася от или към друга таблица.