我自己也是經歷過這問題
我是退伍隔天去辦理護照的地方後面蓋章
後天就去日本玩兩週

最主要是你的護照後面那個
你翻看看 應該有寫 "持照人出國應核准" (好多年了 可能字句不同)
因為我是在當兵的時候辦理新的護照的有蓋這個 你蓋的可能不同 也可以沒蓋 不論如何
你在拿到退伍令 隔天去弄護照的地方蓋章 "持照人身分註銷" 或者類似的可以讓你出機場的! 不會因為沒有服兵役被限制

這是我當年的作法
回來再去鄉公所弄AB(我記得是說十幾天內要去 所以問題不大 我相信各位也不是隔天或者後天就去辦理的)
至於健保...你都要出國 大概很用到 別在日本生病就好