На самом деле вариантов много. На одном сайте, на котором не было полноценной возможности так сделать, но было очень нужно я использовал Nginx rewrite правило
location ~ /(?<city>.*)/catalog/(?<section>.*) {
rewrite /([^/]+)/catalog/([^/]+) /catalog/$section?city=$1 break;
}
Потом в коде страницы где выводится Title и описание я делал к ним дополнение в зависимости от наличия гет параметра. Отсюда ответ на второй вопрос, нет визические страницы создавать не обязательно. Вобще все вши возможности зависят от того на чем работает ваш сайт, на котором вы хотите это сделать. Если это фреймворк то вообще красота.
Но чтобы эти страницы попали в поиск их нужно как минимум указать на странице. Желательно еще и в сайтмап отправить