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