Посмотрите в магазине "Комуфляж и снаряжение" (что-то такое, точное название я не помню) на ул.Некрасова, дом, следующий после общежития ФСБ (короче где-то в начале улицы, если двигаться от Мичурина, маленькое такое крылечко с зеленой вывеской).
Именно НАТО там может и не быть, но я знаю что они принимают индивидуальные заказы на пошив одежды и обуви.

Еще камуфляж есть в Военном универмаге и на ул.Никитина раньше был спецназовкий магазин (если ехать с центра по ул.Кирова, за универмагом Октябрьский нужно повернуть направо и проехать несколько домов, магазин будет по правую руку (вывеска была черно-желто-красная).