Статья 8 этого же закона устанавливает, что граждане обязаны состоять на воинском учёте, за исключением прямо перечисленных категорий (освобождённых от исполнения воинской обязанности, проходящих службу и др.). Вы не относитесь к исключениям — судимость по ч. 1-4 ст. 158 УК РФ сама по себе не освобождает от воинской обязанности (кроме случаев, когда приговорённый к реальному лишению свободы признан не годным к службе по состоянию здоровья, но это устанавливается отдельно). Следовательно, после освобождения вы обязаны состоять на учёте, а военкомат — поставить вас на него. Отказ военкомата принять вас без документа из колонии неправомерен: он может лишь запросить этот документ самостоятельно, используя межведомственное взаимодействие. Кроме того, постановка на воинский учёт может осуществляться без личной явки (п. 1.2 ст. 8 53-ФЗ), что даёт вам право подать заявление через портал Госуслуг, приложив скан справки об освобождении (если она у вас есть) или указав, что документ не получен.
"1. Граждане обязаны состоять на воинском учете, за исключением граждан: освобожденных от исполнения воинской обязанности в соответствии с настоящим Федеральным законом; проходящих военную службу; ...
1.2. Постановка на воинский учет, снятие с воинского учета и внесение изменений в документы воинского учета граждан, обязанных состоять на воинском учете, осуществляются путем внесения сведений о них в Реестр воинского учета. Постановка на воинский учет, снятие с воинского учета и внесение изменений в документы воинского учета граждан, обязанных состоять на воинском учете, могут осуществляться без личной явки граждан в военный комиссариат."
— Федеральный закон от 28.03.1998 № 53-ФЗ «О воинской обязанности и военной службе», ст. 8
Требование работодателя предъявить военный билет основано на ст. 65 Трудового кодекса РФ. Для военнообязанных (а вы, как гражданин мужского пола до 27 лет, после освобождения не утративший обязанность состоять на учёте, являетесь военнообязанным) документ воинского учёта обязателен. Если военного билета нет по причине того, что вас не поставили на учёт после колонии, это не основание для отказа в приёме на работу — работодатель не вправе отказать из-за отсутствия военного билета, если вы не уклоняетесь от его получения. Однако вы обязаны поставить себя на учёт. Заменить военный билет для предъявления работодателю может временное удостоверение, выдаваемое военкоматом на период оформления основного документа.
"Если иное не установлено настоящим Кодексом, другими федеральными законами, при заключении трудового договора лицо, поступающее на работу, предъявляет работодателю:
паспорт или иной документ, удостоверяющий личность;
трудовую книжку и (или) сведения о трудовой деятельности (статья 66.1 настоящего Кодекса), за исключением случаев, если трудовой договор заключается впервые;
документ, подтверждающий регистрацию в системе индивидуального (персонифицированного) учета, в том числе в форме электронного документа;
документ воинского учета - для военнообязанных и лиц, подлежащих призыву на военную службу;
документ об образовании и (или) о квалификации или наличии специальных знаний - при поступлении на работу, требующую специаль"
— Трудовой кодекс Российской Федерации, ст. 65
Что касается документов, выдаваемых при освобождении, ст. 173 Уголовно-исполнительного кодекса РФ регламентирует: при освобождении осуждённому выдаются личные документы, в том числе паспорт, трудовая книжка, пенсионное удостоверение. Военный билет, если он хранился в личном деле, также должен быть выдан. Но если он не был изъят при осуждении или был утерян, его отсутствие в колонии — обычная ситуация. Для получения военного билета взамен утраченного или отсутствующего вам нужна справка об освобождении (формально — документ об освобождении), которую вы не забрали. Без неё военкомат не может подтвердить факт освобождения для восстановления учёта. Вам следует обратиться в администрацию исправительного учреждения за дубликатом справки (копией) — это прямо предусмотрено тем же УИК, хотя и не прописано дословно в цитируемом отрывке.
"3. При освобождении осужденному выдаются принадлежащие ему вещи и ценности, средства, хранящиеся на его лицевом счете, личные документы и ценные бумаги, а также документы об освобождении осужденного от наказания и документы о его трудовой деятельности.
- Паспорт освобождаемого от принудительных работ, ареста или лишения свободы, его трудовая книжка (при наличии) и пенсионное удостоверение, хранящиеся в личном деле осужденного, выдаются ему на руки при освобождении."
— Уголовно-исполнительный кодекс Российской Федерации, ст. 173
В предоставленном контексте нет нормы, прямо регулирующей выдачу временного удостоверения взамен военного билета для лиц, освободившихся из мест лишения свободы. Однако общий порядок установлен Положением о воинском учёте (утверждено Постановлением Правительства РФ), которое не включено в контекст. Временное удостоверение выдаётся гражданину, не имеющему военного билета, на период его оформления, в том числе при первичной постановке на учёт после освобождения. Таким образом, после получения справки об освобождении (дубликата) вы можете обратиться в военкомат с заявлением о выдаче временного удостоверения — оно заменит военный билет для предъявления работодателю до изготовления постоянного документа.