Non dico che debba fare tutto a manina. Dico che esiste la possibilità che alcune cose non sia possibile normalizzarle tramite codice.

Comunque non avendo sottomano i tuoi record ti do un suggerimento un pò sul vago.

Ad esempio, per la tua nuova tabella categorie fai una

select distinct dalla vecchia tabella e la integri dentro l'insert per crearti la nuova tabella di tutte le categorie.

A questo punto nella tabella in cui dovrai mettere l'id corrispondente di quella categoria farai una query di update del genere

codice:
update nuova_tabella,vecchia_tabella
set nuova_tabella.id_cat = vecchia_tabella.id 
where nuova_tabella.categoria = vecchia_tabella.categoria
e così via. Qualcosa magari recuperi.

edit. Per vecchia tabella intendo quella che hai creato tu facendo la select distinct dei tuoi record cui associ un id autoincrementante.