Ganz kurzer Einwand, wie lange hattest du den Hund schon dabei, und es war geduldet, daraus könnte sich unter Umständen schon ein Gewohnheitsrecht ergeben haben. Hast du ne Rechtsschutz?
Gewohnheitsrechte durch zu setzen sind nicht ganz so einfach aber machbar (zwei mal Weihnachtsgeld ohne Hinweis reicht hier schon aus). Falls der Einwand mit dem Mietvertrag allerdings stimmt, dann könnte dies ein Problem werden.
Wenn du eh einen neuen AG haben willst würde ich dir empfehlen dir ein Zeugnis ausstellen zu lassen und dann einfach den Hund mitzunehmen, bis es zur Kündigung kommt. Ist zwar nicht der elegante Weg, aber so hast du Anrecht auf ALG1 und hast noch ein gutes Zeugnis.