Lo que queria era renombrar uno a uno los contactos, mediante el pc y lo he conseguido ya, pero sin utilizar nada de eso.
Dejo aquí el método por si alguien se encuentra en mi misma situación:
Lo que hay que hacer es importar los contactos a gmail, y una vez en el ordenador, borrar y editar todo lo que necesitéis. Cuando hayáis terminado, seleccionamos todos los contactos y le damos a Exportar--> Vcard.
Metemos el archivo que ha creado en la sd, y en contactos, pulsamos menú y le damos a importar desde la SD, cargará tus contactos tal y como los hayas dejado en gmail.
Saludos!