1. SELECT COUNT(DISTINCT `city_id`) AS `city_count` FROM `user_table`;
2. SELECT `user`, COUNT(DISTINCT `city_id`) AS `city_count` FROM `user_table` GROUP BY `user`;
Я стараюсь при разработке структуры базы придерживаться философского «никаких UPDATE'ов — только INSERT'ы». Это делает базу значительно более гибкой. Но соответственно увеличивается количество и сложность (JOIN'ы) SELECT'ов. Если есть запас по производительности, то конечно «вариант 1».