Jeg fandt, at dette fungerede perfekt og ret hurtigt, så her er det:
ALTER TABLE tablename DROP id
ALTER TABLE tablename ADD id INT NOT NULL AUTO_INCREMENT FIRST, ADD PRIMARY KEY (id), AUTO_INCREMENT=1
Jeg ved, at dette ikke er den rigtige tilgang, men for min specifikke situation er det præcis, hvad der var nødvendigt. Der er intet i den tabel, jeg brugte, der henvises til enten fra eller til en anden tabel.