ALTER TABLE User ADD idCity int NOT NULL AFTER Address;

UPDATE User, City
SET User.idCity = City.cityId
WHERE User.City = City.name AND User.Country = City.country;

ALTER TABLE User DROP City;
ALTER TABLE User DROP Country;

ALTER TABLE User ADD KEY (idCity);

SET foreign_key_checks = 0;
ALTER TABLE User ADD FOREIGN KEY (idCity) REFERENCES City (cityId);
SET foreign_key_checks = 1;

CREATE TABLE `Country` (
  `countryId` tinyint unsigned NOT NULL auto_increment,
  `name` varchar(60) default NULL,
  PRIMARY KEY  (`countryId`)
) ENGINE = InnoDB;

INSERT INTO Country (name)
SELECT DISTINCT country FROM City;

ALTER TABLE City ADD countryId tinyint unsigned NOT NULL AFTER name;

UPDATE City, Country
SET City.countryId = Country.countryId
WHERE City.country = Country.name;

ALTER TABLE City DROP country;

ALTER TABLE City ADD KEY (countryId);

SET foreign_key_checks = 0;
ALTER TABLE City ADD FOREIGN KEY (countryId) REFERENCES Country (countryId);
SET foreign_key_checks = 1;