на первый вопрос ответ простой: если вы не будете искать работу и писать бевербунги, то не возьмут.

начинать надо с поиска работы и рассылки бевербунгов.

Вы сразу увидите отклик - отвечают или нет, приглашают на собеседования или нет.

Если вы работу найдёте и подпишете Arbeitsvertrag, только тогда и не раньше наступит время для разговора с шефом.

Время выхода на новую работу обговаривается в процессе переговоров. К этому времени и привязывается Kündigung

старого рабочего договора и квартиры, а так же нахождение новой квартиры.

если в рабочем договоре ничего про Kündigungsfrist не стоит, то действует закон:

Der gesetzliche Standard ist: Sie können als Arbeitnehmer mit einer Frist von vier Wochen zum 15. oder zum Ende des Kalendermonats kündigen. Diese Frist kann durch den Arbeitsvertrag nicht verkürzt, aber verlängert werden.

если квартира сразу не находится, то можно пожить в пенсионе или вести doppelte Haushaltsführung и в это время искать подходящую квартиру.

Кошки могут стать проблемой, которую вам надо решить.