Верно, запятая нужна: она закрывает придаточную часть какой же он все-таки плохой.
Корректно: город с более чем 130-летней историей.
Слова "тем не менее" не используются как вводные.
ТЕМ НЕ МЕНЕЕ, частица и союз
1. Частица (часто в сочетании с противительными союзами «а», «но», а также в предложениях с союзами «хотя», «несмотря на то что», «пусть» и др.). Не требует постановки знаков препинания.
Мюллер долго наблюдал за тем, как медленно, еле заметно, но тем не менее неуклонно лучи двигались по комнате. Ю. Семенов, Экспансия-I. Несмотря на то, что Ягозин был кровным детищем Петербурга… он весь тем не менее состоял из одной быстроты и юркости. Д. Григорович, Карьерист.
2. Союз (между частями сложносочиненного предложения). То же, что «но, однако».
…Это были все-таки карты, несколько захватанные, затертые пальцами по краям, тем не менее невозможно было представить, что в них играли за столом... Ю. Бондарев, Горячий снег.
Запятая не нужна.
Как правило, слова тем не менее не выделяются.
Слова тем не менее обычно не обособляются, хотя иногда их выделяют как вводные при соответствующей интонации.
Обособление не требуется. Вместо "в связи с тем" лучше сказать "в связи с этим".
Если придаточная часть сложноподчиненного предложения стоит перед главной, запятая между частями союза перед тем как обычно не ставится. Запятая после придаточной части (после ПО) нужна.
