Чем заменить ZeroTier или Hamachi, если они не работают у провайдера?

Это решает ту же задачу — объединяет машины за NAT в одну локальную сеть, — но идёт по обычному HTTPS на порт 443. Для сети снаружи это соединение с сайтом, а не VPN-протокол: опознавать нечего и отсекать нечего. Ни аккаунта в чужом облаке, ни ограничения по числу машин.

Как подключиться к компьютеру за NAT без «белого» адреса?

Обе машины сами подключаются наружу к серверу и встречаются на нём. Ни проброса портов, ни статического адреса, ни настройки роутера — работает и за мобильным модемом, и за общим адресом провайдера.

Это то же самое, что удалённый терминал?

Терминал здесь есть — SSH из браузера к любой Linux-машине, — но задача шире. Кроме консоли вы получаете полноценную локальную сеть: общие папки, «Сетевое окружение», принтеры, удалённый рабочий стол и всё прочее поверх Ethernet.

Что нужно, чтобы поднять свой сервер?

Самый дешёвый VPS с доменным именем: одно ядро и 512 МБ памяти. Сценарий установки заводит службу, настраивает nginx и получает сертификат Let's Encrypt. Сервер — один файл, база — SQLite рядом.