1. В рамках одной таблицы city это никак не сделать, всё равно придется в дочерних таблицах переставлять значения в Foreign Key с дубликатов на правильный оставшийся город. Можно написать хранимую процедуру, которая будет принимать список дубликатов (а поиск дубликатов предварительно будет осуществляться, например, регуляркой), выбирать единственное верное значение (возможно (и лучше) с вашей подсказкой), во всех дочерних таблицах переставлять значения в Foreign Key на запись с этим значением, а затем удалит дубликаты из city.
2. UUID нужен для распределенных систем, где нет возможности выполнить проверку уникальности первичного ключа в рамках всей системы или если у вас к базе идет большое кол-во запросов на запись, настолько большое, что СУБД просто не успевает выполнить проверку уникальности первичного ключа для каждой записи. Но, как я понимаю, это не ваш случай. В данном случае вместо 16-байтового UUID лучше использовать автоинкрементное, целочисленное, беззнаковое, 2-байтное поле (city_id SMALLINT UNSIGNED NOT NULL AUTO_INCREMENT PRIMARY KEY). Зачем использовать 16-байтный первичный ключ, когда достаточно 2-байтного? Быстрее будут исполняться JOIN'ы, меньше операций ввода/вывода с диска, меньше требуемого места для хранения на диске.