I do something similar. I run a nebula network. The vps has haproxy and is passing the encrypted data to the hosts using sni to figure out the specific host. No keys on the vps.
The vps and each host are each nebula nodes. I can put the nodes wherever i want. Some are on an additional vps, some are running on proxmox locally. I even have one application running as a geo-isolated and redundant application on a small computer at my friend’s house in another state.
Headscale [1] has a stronger claim to "free version of Tailscale" - it's literally a self-hosted version of Tailscale's coordination server. It's even compatible with the Tailscale client.
The problem with Headscale is that it has absolutely no documentation. All of it is described in relation to Tailscale, which is what I don't want to use. Here are the Tailscale features we have, here are the differences with Tailscale. It's very weird.
The vps and each host are each nebula nodes. I can put the nodes wherever i want. Some are on an additional vps, some are running on proxmox locally. I even have one application running as a geo-isolated and redundant application on a small computer at my friend’s house in another state.