Согласно правилам, оба названия склоняются: в г. Нижнем Тагиле, в г. Каменске-Уральском_ (первая часть тоже склоняется). Подробнее см. в «Письмовнике».

Слово чтобы в данном предложении является подчинительным союзом, который всегда пишется слитно. Раздельно пишется местоимение что с условной частицей ​​​​​​​бы (но я не могу сказать, что бы тебе следовало сделать).

Да, правильно понимаете.

Действительно, в некоторых словах историческая приставка с- (со-) в современном русском языке может не выделяться, если утрачена структурно-смысловая связь с родственными словами без этой приставки. Так, А. Н. Тихонов в своем «Морфемно-орфографическом словаре» не выделяет приставку в словах созерцание, созерцать, так как в русском языке нет глагола зерцать, глагол созерцать непроизводный. Но в том же словаре выделена приставка в словах сотворение, сотворить, так как последнее образуется от глагола творить. Иной подход к морфемному членению слов, учитывающий ощущаемые носителями языка исторические смысловые связи, позволяет выделить приставку и в слове созерцать (см., например, ресурс «Портрет слова» на сайте Национального корпуса русского языка или «Орфографическое комментирование русского словаря»). На нашем портале морфемный состав многих слов показан в конце статей «Большого универсального словаря русского языка» под ред. В. В. Морковкина. И в заключение заметим, что приставка с- (со-) имеет разные значения, они описываются в толковых словарях. Наиболее подробное словарное описание можно прочитать в «Большом академическом словаре русского языка». 

Нет, такие сочетания не соответствуют нормам современного русского литературного языка, хотя многие лингвисты отмечают экспансию предлога на в разговорной речи. 

"...предлог на, как, например, приставка про- (всякие там пролечить, проплатить), в последнее время замелькал довольно активно: на тюрьме (как на зоне), на вагоне (Кипяток попросите на соседнем вагоне — недавно в поезде услышала), на районе (даже в какой-то рекламе было: У нас на районе никто не зажигает). А мое любимое выражение с предлогом на — на позитиве: Я пришел такой весь на позитиве. Раньше говорили на нервах, на голубом глазу, а теперь еще и на лавэ (то есть, при деньгах). <...> Вот в каком-то блоге обсуждают фотографию приятеля: смотри, мол, какой нарядный, на костюме (далее непечатно). Или вот по поводу дресс-кода: обязательно ли в этой фирме ходить на костюме, на галстуке? Попутно выяснила, что выражение на галстуке есть еще в жаргоне автомобилистов: в смысле машина заглохла, пришлось ехать на галстуке" (И. Левонтина. Русский со словарем. М., 2016). 

Нет, такие сочетания не соответствуют нормам современного русского литературного языка, хотя многие лингвисты отмечают экспансию предлога на в разговорной речи. 

"...предлог на, как, например, приставка про- (всякие там пролечить, проплатить), в последнее время замелькал довольно активно: на тюрьме (как на зоне), на вагоне (Кипяток попросите на соседнем вагоне — недавно в поезде услышала), на районе (даже в какой-то рекламе было: У нас на районе никто не зажигает). А мое любимое выражение с предлогом на — на позитиве: Я пришел такой весь на позитиве. Раньше говорили на нервах, на голубом глазу, а теперь еще и на лавэ (то есть, при деньгах). <...> Вот в каком-то блоге обсуждают фотографию приятеля: смотри, мол, какой нарядный, на костюме (далее непечатно). Или вот по поводу дресс-кода: обязательно ли в этой фирме ходить на костюме, на галстуке? Попутно выяснила, что выражение на галстуке есть еще в жаргоне автомобилистов: в смысле машина заглохла, пришлось ехать на галстуке" (И. Левонтина. Русский со словарем. М., 2016). 

При собственно морфемном анализе в слове чересчур выделяют приставку черес- и корень -чур, см. «Словарь морфем русского языка» А. И. Кузнецовой и Т. Е. Ефремовой.

Если ограничиться синхроническим словообразовательным анализом, то основу чересчур принято рассматривать как нечленимую, см. «Словообразовательный словарь русского языка» А. Н. Тихонова. По мнению автора словаря, утрата семантических связей с морфемами, на основе которых образовалось слово, означает, что оно превратилось в непроизводное. В соответствии с концепцией словаря, непроизводность подразумевает нечленимость, хотя такой подход в языкознании является предметом дискуссий.

Этимологически слово чересчур образовано на базе предложно-падежного сочетания черес чур (чур в зн. ‘черта, край’). Ср. использование корня -чур- в чураться, тоже образованного от существительного чур (‘черта, край’). Чураться буквально — ‘ограждать себя словом чур от нечистой силы’ (см. «Этимологический словарь русского языка» Н. М. Шанского и Т. А. Бобровой). В современном языке сохранилось междометие чур, означающее требование соблюсти какой-либо уговор.

В полном академическом справочнике «Правила русской орфографии и пунктуации» под ред. В. В. Лопатина по поводу оборотов с предлогом кроме сказано следующее: «Оборот с предлогом кроме имеет два значения: а) одно совпадает со значением слов за исключением, т. е. имеет значение исключения из ряда подобных предметов: На всех берегах залива на протяжении сотен верст мною не было встречено ни одного человека, и, кроме горчайшей полыни и сухого бурьяна, я не сорвал ни одной травинки (Пауст.); Вершинин отправил луговиков в институт, всех, кроме Свиридовой, — ее он включил в высокогорный отряд (Зал.); б) другое — это обозначение включения в ряд подобных предметов: У Бунина, кроме блестящих, совершенно классических рассказов, есть необычайные по чистоте рисунки (Пауст.); Я слышал, кроме гудения мотора, еще несколько звуков (Пауст.).

В настоящее время различия в значениях оборотов со словом кроме не сказываются на пунктуации: и в том и в другом случае предусмотрено выделение запятыми. Однако в прошлом обороты со значением включения знаками препинания не выделялись. Ср.: Кроме учителей на собрание пришли и ученики. — Кроме учителей, на собрание никто не пришел».

В соответствии с рекомендацией справочника в Вашем случае обособление нужно.