Игорь, доброго утра! В вашей ситуации есть 2 варианта действий и оба они привязаны к месту регистрации:
1) вы возвращаетесь в свой регион по прописке и там подаете в первую очередь заявление в военкомат на восстановление военного билета, затем в паспортный стол на смену фамилии и после получения нового паспорта осуществляете смену всех документов.
2) вы в первую очередь прописываетесь в регионе, где сейчас проживаете. После этого по месту новой прописки вы обращаетесь в военкомат на выдачу военного билета, далее меняете фамилию и все остальные документы.
Все действия осуществляются исключительно в заявительном порядке, т.е. без вашего участия и ваших соответствующщих заявлений ничего не сдвинется с места.
