Sądzę, że to da się zrobić w JS, ale jeśli będzie to zrealizowane w HTML to nie będzie mi przeszkadzało, a nawet bardziej mi się spodoba.
podstawowy błąd - usilnie zapinasz się już na starcie ze chcesz problem X rozwiązać w technologii Y. Nigdy tak nie rób. Zawsze najpierw analizuj dokładnie tzw. założenia biznesowe problemu a dopiero potem dobieraj do tego technologię.
A co do problemu to możesz np. nasłuchiwać na keydown i dodawać dynamicznie myślnik ale to nie jest do końca dobre rozwiązanie - w sensie ogólne założenie z tym myślnikiem. Taka forma zapisu kodu pocztowego nie występuje w każdym kraju i swoją implementacją mocno ograniczasz możliwości wpisywania kodu przez obcokrajowców.
Jeśli już się na to upiersz to daj dodatkowo np. pole na wybór kraju, by default ustawione na Polskę i tylko dla PL odpalaj taką waildację podczas wpisywania. Poczytaj sobie o zdarzeniach w JS i ich obsłudze. Ciężko coś konkretniej doradzić bo nie wiem na jakim jesteś poziomie z JS.