Слово Тюмень в сочетании с существительным город должно склоняться: в городе Тюмени, городом Тюменью.
Тюмень женского рода.
Ничего не изменилось. Верно: из города Москвы, Саратова, Тюмени. Подробнее см. в "Горячих вопросах".
Через тире с пробелами: Тюмень – Омск.