Así es .. con una sóla sentencia SQl lo podrías resolver.
En SQL tienes funciones para manejar Strings (cadenas) al igual que en PHP o cualquier otro lenguaje de programación, hasta tienes posibilidad de usar expresiones regulares incluso. Se trata de usarlas en el "UPDATE", sin "condicional" (para que aplique a toda la tabla) y sin cambiar el tipo de dato de tu campo "fecha" actual (un varchar()) hasta que termines el proceso.
Es decir .. aplicas un UPDATE tipo:
Código PHP:
UPDATE tabla SET fecha=CONCAT(SUBSTRING(fecha,6,9),'-',SUBSTRING(fecha,3,4),'-',SUBSTRING(fecha,0,2))
(no me he puesto a probarlo ni he contado bien los rangos de los caracteres que necesitas .. pero por ahí va el tema. Seguro que tiene várias soluciones en SQL este problema .. sobre todo con expresiones regulares incluso ...)
más info:
http://dev.mysql.com/doc/refman/5.0/...functions.html
Y luego cambias el tipo de campo a un "DATE".
Un saludo,