Не хотят ставить на воинский учет без временной регистрации

Можете.

П.2 ст. 8 ФЗ «О воинской обязанности и военной службе» очень вменяемо объясняет, что

Отсутствие у граждан регистрации по месту жительства и месту пребывания не освобождает их от обязанности состоять на воинском учете и не может служить основанием для отказа в постановке их на воинский учет.

Есть только одно изъятие из этой нормы, п.3 той же статьи — офицеры запаса ФСБ и СВР,

Советую обращаться в письменной форме с требованием поставить вас на воинский учет, но при этом, поскольку вы не призывник, то предварительно обязаны сняться с воинского учета в старом военкомате.