Да, склоняются, хотя это явная примета разговорного стиля речи.
Употребляются варианты Гагра и Гагры (второй вариант отражен в названии известного фильма «Зимний вечер в Гаграх»). Но словарями русского языка зафиксировано: Гагра, такое же название употребляется в картографических изданиях Росреестра. Это склоняемое существительное: поехать в Гагру, отдыхать в Гагре, сказочная Гагра.
Правильно: Редкая гадина была. Губчека.
Герр – склоняемое существительное: у герра Миллера, к герру Миллеру.
Верно: Габриеля Гарсиа Маркеса, Габриелю Гарсиа Маркесу и т. д.
Некоторые словари фиксируют написание Гарсия — в этом случае склоняются все три слова.
Корректные варианты: Следующая остановка: «Улица Михаила Дудина». Следующая остановка — «Улица Михаила Дудина». Следующая станция: «Академическая». Следующая станция — «Академическая».
В обычных повествовательных текстах лучше писать с тире.
Скорее всего, просто шутливая рифма. В. И. Даль поясняет: Досталася (достается и) гадине виноградина - говорится о замужестве.
Следует, правда, пояснить, что у Даля "гадина ж. или гад м. ползучее животное, пресмыкающееся, противное человеку; это земноводное либо насекомое, собств. земноводное; их четыре отдела: змея, лягушка, черепаха, ящерица. || Бран. мерзавец, сквернавец".
