Можно выписаться из квартиры и прописаться по другому адресу без военного билета?

Понятие «прописка» в действующем законодательстве не применяется, это регистрация по месту жительства.
По существу Вашего вопроса:
-в соответствии с действующим законодательством - да, можно,
-в соответствии со сложившейся практикой - нет, не получится.

ПРАВИЛА
РЕГИСТРАЦИИ И СНЯТИЯ ГРАЖДАН РОССИЙСКОЙ ФЕДЕРАЦИИ
С РЕГИСТРАЦИОННОГО УЧЕТА ПО МЕСТУ ПРЕБЫВАНИЯ И ПО МЕСТУ
ЖИТЕЛЬСТВА В ПРЕДЕЛАХ РОССИЙСКОЙ ФЕДЕРАЦИИ

16. Гражданин, изменивший место жительства, обязан не позднее 7 дней со дня прибытия на новое место жительства обратиться к должностным лицам, ответственным за регистрацию, и представить:
документ, удостоверяющий личность;
абзац исключен. - Постановление Правительства РФ от 14.08.2002 N 599;
заявление установленной формы о регистрации по месту жительства;
документ, являющийся в соответствии с жилищным законодательством Российской Федерации основанием для вселения в жилое помещение.

Второй абзац, исключенный Постановлением Правительства РФ от 14.08.2002 № 599, звучал так:
"военный билет (временное удостоверение взамен военного билета) или удостоверение гражданина, подлежащего призыву на военную службу, - для лиц, обязанных состоять на воинском учете".

Но в том-то и дело, что исключили, а на практике требуют.
Прошло почти 7 лет, а правоприменительная практика не изменилась.

Если для Вас это принципиальный вопрос, обжалуйте отказ в суде. Но стоят ли того затраты (времени, нервных клеток, денег на представителя и т. п. ) на судебное разбирательство? Может быть проще получить военный билет?

Такой отказ неправомерен. Ранее была такая обязанность в Правилах регистрации граждан и суд уже отменил этот пункт об обязательном требовании справки-таллона о снятии, постановке на воинский учет.
Я выписывался и регистрировался принципиально не давая им такую справку. Конечно возмущались но сняли и поставили на регистрацию. Обязаность же сняться и встать на воинский учет у тебя остается по закону РФ "О воинской обязанности и военной службе" и штраф за неисполнение (КоАП РФ) , но это уже не забота паспортных столов.
Если хочешь посудиться - обратись в райсуд с иском на ЖКХ или какая там у Вас организация в ведени которой находится Паспортный стол. Для этого нужна госпошлина-100р..

напиши письмо с просьбой о выписке (тока граматно) и пошли по почте с уведомлением о вручении. в письме укажи, что просишь обяснить причину отказа в случае отказа. также пометь, что копия письма осталась у тебя. в случае отказа смело подавай в суд. но лучше реши полюбовно, т. к. с воинского учета сняться все равно надо будет и встать потом тоже. если не встанешь на воинский учет позабыл в какой срок-- штраф 1000р.