Как наложить нетривиальное ограничение уникальности на поле?

Ограничение уникальности накладывается на поля в рамках одного отношения, то есть то что вам хочется провернуть, а именно заглянуть как-то в другую табу чтобы проверить уникальность, из коробки такой возможности нет. Два наиболее очевидных способа решения задачи:
1) Прокинуть city_id в нужную таблицу. Да, не по феньшую, но реальность такая что нормализованные базы данных существуют только в книгах по базам данных или во всяких простячковых проектах, добро пожаловать.
2) Оставить все по феньшую и просто повесить триггер, в котором и будет происходить проверка уникальности по городу.

Создавать связь по city_id плохой вариант. Да, вы решите вопрос с уникальностью, но потеряете принадлежность районов к определенному городу в рамках таблицы ТР.
Поэтому решайте с помощью внешнего языка программирования или хранимых процедур. Триггеры не очень явная штука, я бы лучше создал отдельную процедуру для заведения новых ТР, если выберите 2 вариант.