La formule est correcte et on la trouve dans la littérature, même si elle semble assez moderne  (voir des attestations ici).  Avec un singulier on emploiera  par (une fois par an) mais cela n’est pas d’usage avec un pluriel. Je ne vois donc pas d’autre solution simple.

Pourquoi ajouter « une fois » ?
Ils se contentaient de la rencontrer tous les quelques mois.
Une fois n’apporte rien. Une fois, ce peut être un jour, une heure, une semaine, dix minutes. Rien n’empêche de préciser la durée. 
Ils se contentaient de la rencontrer une heure/un jour/etc. tous les quelques mois.