Zerotier parece se encaixar perfeitamente no seu caso de uso:
Eles chamam isso de "Rede Definida por Software". É uma mistura entre VPN e serviços como o Hamachi. Basicamente, você precisa criar redes (que possuem IDs exclusivos), às quais você pode conectar e autorizar dispositivos. É uma rede P2P, mas pode usar supernós se sua rede não permitir conexões de entrada.
Atualmente, eles suportam vários sistemas operacionais: Linux, FreeBSD, Android, Windows, OSX.
Com exceção do Android, você também pode se conectar a várias redes de uma só vez. Conectar-se a uma rede cria uma placa de rede virtual no seu sistema operacional.
Você também pode usar o zeroconf ou algo assim se quiser usar o DNS.
É baseado em UDP e lida muito bem com mudanças de rede. Eu experimentei isso muitas vezes com meu celular mudando de wifi (s) para LTE e vice-versa.