If you “always” have Internet access, you should really just place ntpd onto the physical network where it belongs. Otherwise, the options are all mentioned in the article (and might be used in your distribution).
— Restoring more sane shutdown timestamp from file instead of just using 1980.
— Making blind single use ntpdate request to some public server to set local time after the network is available, but before any other application uses it. There might be appropriate hooks in your init system if you don't want to make it an independent step.
— The same, but using some local time source. It is not widely known that even plain old Windows desktops, while not having a complete NTP server, can be trivially configured to announce time over some form of SNTP. If you have any computer with a real clock running nearby, you can probably rely on it. Next step router is also a good potential candidate.
As for compartments and access control, you can try to use basic VLANs (one for ntp traffic, and only it, and one for VPN) or maybe some two-step network configuration process (get time with one configuration, reset and proceed with other services).
All of that is not a problem, the problem is what to do when something fails. Time server becomes unavailable, intermittent internet connectivity, server you use for pings is available, but others are not, etc. You can choose to stop completely if there is no time source, and wait, but that might render the system unavailable for remote configuration. You can try to restart the device or restart the network router automatically (though only a fixed number of times, restart loop will surely break something), but that won't help if the problem gets fixed some time later. You can also use a fallback configuration that doesn't depend on correct time (e. g. only start an ssh server so you can connect to it).