Un ALTER TABLE istruzione aggiungendo la PRIMARY KEY la colonna funziona correttamente nel mio test:
ALTER TABLE tbl ADD id INT PRIMARY KEY AUTO_INCREMENT;
Su una tabella temporanea creata a scopo di test, l'istruzione sopra ha creato l'AUTO_INCREMENT id colonna e inseriti valori di incremento automatico per ogni riga esistente nella tabella, a partire da 1.