И все же, как ни выгораживал Старостина генерал Бурдаков, в Хабаровск тому ехать пришлось. Кстати, в пути Николай случайно встретился со своим братом Александром, который направлялся этапом в Соликамск.
По дороге к месту назначения со Старостиными неоднократно могла случиться беда, но не случилась, поскольку уголовники тоже уважали легендарных братьев-спартаковцев. По словам Николая, «принадлежность к футболу была лучшей охранной грамотой. Когда вечерами по просьбе своих соседей по нарам я начинал вспоминать футбольные истории, игра в карты сразу прекращалась. Самые отпетые рецидивисты тихо, как примерные школьники, слушали мои рассказы. Я мог жить – не тужить…»
В Хабаровск Николай Старостин прибыл 8 мая 1945 года. На следующий день весь мир узнал о том, что война закончилась, и у миллионов заключенных в советских лагерях появилась надежда, что их участь изменится к лучшему. Но эти надежды оказались напрасными – война войной, но и осваивать Сибирь кому-то надо было.
Несмотря на то что Гоглидзе был другом Берии, даже он не решился с ходу назначить Старостина тренером хабаровского «Динамо». Поэтому временно отправил его в Комсомольск-на-Амуре, в тамошнее «Динамо». Там Старостина взял под свою опеку начальник Амурлага генерал Петренко. Положение Старостина облегчало еще и то, что к нему разрешили приезжать из Москвы его жене и дочке.
В 1948 году судьба Николая Старостина могла круто измениться. В Москве объвился еще один футбольно-хоккейный меценат – сын самого вождя народов Василий Сталин, который решил бросить вызов Берии. Под его руководством была сформирована команда ВВС, куда он стал набирать лучших игроков со всей страны. Тренером футбольной команды Василий решил заиметь нашего героя – Николая Старостина. К тому времени тот уже считался досрочно освобожденным, однако в списке городов, куда он не имел права приезжать, значилась Москва. Но для сына Сталина запретов не существовало. Поэтому в один из дней он прислал за Старостиным свой личный самолет (Василий тогда занимал пост командующего ВВС Московского военного округа), который и доставил Николая в столицу. В тот же день ему восстановили в паспорте его московскую прописку – Спиридоньевская улица, 15, квартира 13. Однако радость Старостина длилась недолго – всего два дня. Потом к нему домой явились люди в штатском (посланцы Берии) и объявили, что его прописка аннулирована и ему необходимо немедленно возвращаться либо обратно в Комсомольск-на-Амуре, либо в любой другой город, где ему разрешается проживать. Старостин выбрал Майкоп. Однако, прежде чем уехать, он решил в последний раз наведаться к Василию Сталину.
Когда сын вождя узнал, что произошло со Старостиным, он был вне себя от гнева. «Как они посмели без моего ведома давать указания моему работнику!» – бушевал Василий. И тут же приказал Старостину переселиться к нему, в особняк на Гоголевском бульваре. «Здесь вас не достанут, – заявил Василий. – А я пока утрясу вашу проблему». По словам Старостина: «Василий Сталин решил бороться за меня не потому, что добивался торжества справедливости. Я был ему нужен как тренер. Но сейчас и это отошло для него на задний план. Суть заключалась в том, что он ни в чем не хотел уступать своему заклятому врагу – Берии, которого люто ненавидел, постоянно ругал его последними словами, совершенно не заботясь о том, кто был в тот момент рядом. Я несколько раз пытался остеречь его, говоря: «Василий Иосифович, ведь все, что вы произносите, докладывают немедленно Берии». – «Вот и хорошо, пусть послушает о себе правду и знает, что я о нем думаю», – отвечал он…»
Поскольку угроза Старостину со стороны Берии продолжала сохраняться даже в особняке сына вождя, ему приходилось несладко: он вынужден был как прикленный всюду следовать за Василием, и даже ночью они спали вместе, благо широкая кровать это позволяла. Причем Василий обязательно клал под подушку взведенный пистолет. Выйти из особняка в одиночку Старостин опасался, поскольку однажды заметил на противоположной стороне улицы двух субъектов в штатском, внимательно следивших за подъездом особняка. Однако увидеть жену и дочерей Старостину жуть как хотелось. И однажды он не выдержал.
В одну из ночей, когда Василий изрядно набрался (а к тому времени он уже был законченным алкоголиком), Старостин бесшумно выскользнул из особняка и рванул к себе на Спиридоньевку. Только зря он надеялся перехитрить ищеек Берии, которые прекрасно понимали, чем им могла грозить такая оплошность – упустить из виду объект слежки. Старостин пробыл в родном доме всего лишь несколько часов. Ровно в шесть утра в дверь позвонили, и, когда он открыл, на пороге возникли мрачные субъекты в штатском. Они приказали Старостину одеться и лично повезли его на вокзал, чтобы оттуда прямиком отправить в Майкоп. Но Берия допустил ошибку: надо было везти Старостина самолетом, а не поездом. Поскольку уже в Орле поезд догнал начальник контрразведки Василия Сталина (догнал на самолете) и заставил Старостина вернуться в Москву. Но детективная история на этом не закончилась.
Василий, взбешенный поступком Берии, который он расценил как личное оскорбление, решил ответить тем же. Едва Старостин появился на пороге его особняка, сын вождя повез его на стадион «Динамо», где хозяева принимали его команду ВВС. Зная, что на матче обязательно будут люди Берии, Василий хотел показать им Старостина и тем самым взять реванш за свое недавнее унижение. И все же победа в итоге осталась за Берией. Тот воспользовался тем, что Василий в те дни находился в опале после одного трагического случая (будучи на рыбалке, он с друзьями глушил рыбу гранатами, и по пьянке один из глушивших – личный пилот Василия – погиб), и лично доложил Иосифу Сталину (они оба в те дни отдыхали в Пицунде) о том произволе, который творит его сын: прикрывает ссыльного осужденного. И вождь взял сторону Берии. Узнав об этом, Василий самолетом рванул к отцу, но тот не принял сына, выставив вперед врачей, которые объявили, что вождь народов плохо себя чувствует. И Василий понял, что сражение за Старостина проиграл. Поэтому, когда Николай позвонил ему из Москвы и сообщил, что устал от сложившейся ситуации и вылетает в Крым, Василий возражать не стал.
Расплата за московскую эпопею не заставила себя долго ждать. Берия вновь явил Старостину свою злопамятность и сделал так, что его осудили на пожизненную ссылку в Казахстан. Правда, и там Старостин без любимого дела не остался: в Алма-Ате он поднимал тамошние футбол и хоккей. Там его и застал июнь 1953 года. В том месяце арестовали Берию, и «дело братьев Старостиных» вскоре было пересмотрено. К тому времени Андрей Старостин жил в Норильске, Андрей – в Соликамске (ему пришлось тяжелее всех – он работал на лесоповале), Петр – под Тулой, где работал начальником ОКСа. В марте 1955 года уголовное дело братьев Старостиных было прекращено и им разрешили вернуться в Москву.