На виртуальном приватном серваке можно замутить сервис виртуальной частной сети, а что тут не возможного?
В широком смысле - да. На впске за три бакса - нет, там скорее всего тупо нет модуля ведра tun/tap. Хостер его едва ли включит. Более того, под openvz некоторые модули непредскауемо глючат и тупят, но tun работает.