Какие нормы склонения фамилий действуют в украинском языке, мы не знаем (этот вопрос Вы можете задать нашим украинским коллегам). Но по нормам русского языка мужская фамилия Дзюб склоняется. Это отнюдь не «новые правила»: если в других документах на русском языке фамилию не склоняли, объяснить это можно только неграмотностью сотрудников, выдававших документы.

Фамилии на -ых, -их – единственное исключение. Все остальные мужские фамилии на согласный (независимо от их происхождения) склоняются – это закон русской грамматики.

Все фамилии, кончающиеся на неударное а после согласных, склоняются по первому склонению: Рибера — Риберы, Рибере, Риберу, Риберой, Сенека — Сенеки и т. д.; так же склоняются Кафка, Спиноза, Сметана, Петрарка, Куросава, Глинка, Дейнека, Гулыга, Олеша, Нагнибеда, Окуджава и др. Все такие фамилии, независимо от происхождения, являются морфологически членимыми в русском языке, т. е. в них выделяется окончание -а. Склонение фамилий, оканчивающихся в исходной форме на гласные, не зависит от того, мужские они или женские.

Название Тускарь, судя по данным Национального корпуса русского языка, встречается в текстах XVIII века (В. Ф. Зуев. Путешественныя записки Василья Зуева отъ С. Петербурга до Херсона въ 1781 и 1782 году), в биографических «Записках актера Щепкина», в произведениях Фета, Лескова, Гиляровского. Во всех этих текстах название реки употребляется как слово женского рода. В русском языке есть некоторое количество слов женского рода на -арь (бездарь, гарь, марь, киноварь, утварь, хмарь и др.).

Употребление слова город (и сокращения г.) перед названием города – характерная черта канцелярской речи, поэтому в «Справочнике издателя и автора» А. Э. Мильчина, Л. К. Чельцовой дана рекомендация употреблять сокращение г. (и полное слово город) ограниченно, преимущественно перед названиями городов, совпадающими с фамилиями людей, напр. г. Пушкин, г. Королев. Однако на практике эта рекомендация редко соблюдается,  сокращение г. и полное слово город употребляют перед названиями всех городов.

Этот словарь составляла Т. Ф. Ефремова. Подобные значения зафиксированы и в «Большом толковом словаре русского языка» под ред. С. А. Кузнецова. В нём приводятся такие примеры: Зыбь на озере. Зыбь осеннего поля. Рожь подёрнулась зыбью. Смиренный парус рыбарей... Скользит отважно средь зыбей (А. С. Пушкин).

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

Действительно, Ё пишется в обеих частях названия: Хорошёво-Мнёвники.

По одной из версий, название села Хорошёва возникло от мужского имени Хорош, по другой – от слова хорошо. Принцип, по которому при историческом образовании географических названий и, например, фамилий фиксировался тот или иной вариант ударения, определить затруднительно.

Что касается выбора между О и Ё, то в русских названиях, как и фамилиях, на шипящий + -ов (-ёв) пишется О или Ё в соответствии с традицией и с регистрацией в официальных документах.

Женская фамилия Кравец не склоняется, мужская склоняется. Возможно два варианта склонения: Кравеца, Кравецу, Кравеца, Кравецем, о Кравеце или Кравца, Кравцу, Кравца, Кравцом, о Кравце. Ввиду того, что фамилии выполняют юридическую функцию, предпочтительно склонять их без выпадения гласного, то есть использовать первый ряд форм. Правила склонения фамилий на согласную можно прочитать в «Словаре собственных имен русского языка» Ф. Л. Агеенко (пп. 4.1–4.3). Вопрос о действительности документов, в которых фамилия записана в неправильной форме, нужно задать юристам.

Название склоняется и при наличии родового слова город (г.): в г. Владивостоке.

Что касается необходимости родового слова: А. Э. Мильчин и Л. К. Чельцова в «Справочнике издателя и автора» отмечают, что «сокращение г. (город), как и полное слово, рекомендуется употреблять ограниченно, главным образом перед названиями городов, образованными от фамилий (г. Киров)».

Таким образом, правильно и общеупотребительно: во Владивостоке. А варианты в г. Владивостоке, в городе Владивостоке  следует характеризовать как специфически канцелярские (т. е. употребительные преимущественно в официально-деловой речи).

Исключения «придумывает» язык. Фамилии на -ых (-их) типа Золотых, Седых, Долгих являются единственным исключением из правила, гласящего, что склоняются все мужские фамилии, оканчивающиеся на согласный звук. Эти фамилии несклоняемы, потому что они в каком-то смысле уникальны: они происходят от формы родительного (и предложного) падежа множественного числа имен прилагательных. В этом их принципиальное отличие от фамилий на -ич, -ец, -чик  и т. п., которые могут и должны склоняться. Самостоятельно объявить свою фамилию несклоняемой вопреки законам русской грамматики нельзя. 

Действительно, в "Справочнике издателя и автора" А. Э. Мильчина, Л. К. Чельцовой дана рекомендация употреблять сокращение г. (и полное слово город) ограниченно, преимущественно перед названиями городов, совпадающими с фамилиями людей, например г. Пушкин, г. Королев.

Однако на практике (в канцелярской речи) сокращение г. и полное слово город употребляются перед названиями всех городов, в т. ч. с формантами -бург, -град и -город, напр.: г. Волгоград, г. Санкт-Петербург, город Шлиссельбург, город Калининград.