Что прям так строго, не дольше чем 2 месяца?
А у меня 2,5 месяца прошло..

60 дней строго с даты получения гражданства (вручения Einbürgerungsurkunde). Для проверки этого факта консульства и требуют показать Einbürgerungsurkunde при подаче уведомления. Если у вас уже прошло 2.5 месяца, то с вероятностью 99% в консульстве ваше уведомление не примут. Но если вам ехать не далеко и не сложно, можете попробовать, и пожалуйста расскажите тут о результате.

В соответствии с буквой закона, для подачи уведомления у вас остается второй вариант - в течение 60 дней с момента следующего въезда в Россию. На территории РФ уведомление подается в любой отдел полиции (МВД) по вопросам миграции. Прописка не нужна. Но там могут быть чисто практические проблемы:

(1) у этих отделов зачастую странное время приема посетителей - что-то вроде 4 часа в день, не каждый день, и то вечером, то утром. В остальное время, полагаю, они обслуживают обращения через Госуслуги. Поэтому могут быть очереди, и визит к ним надо планировать. Возможно не получится попасть с первого раза, и придется приходить в другой день.

(2) в некоторых (региональных) отделах МВД для подачи уведомления незаконно требуют предъявить внутренний паспорт РФ, хотя загранпаспорта по закону достаточно. Если будут проблемы такого плана, и если у вас нет внутреннего паспорта, то, возможно, придется его оформлять. Прописка для этого не потребуется, но добавьте ещё 5 рабочих дней на данную процедуру.

Впрочем, есть ещё возможность подать уведомление электронно через Госуслуги. Но для этого у вас должна иметься подтверждённая учётная запись привязанная к действующему _российскому_ мобильному телефонному номеру. Если Госуслуг нет, то можете попытаться зарегистрироваться на них по приезде в РФ, но для этого, опять же, нужны российский внутренний паспорт, и _российский_ мобильный телефонный номер (а с оформлением оного сейчас могут проблемы, возможно нужна регистрация по месту пребывания).