VirtualBox хорошо работает и на MacOS X и на Ubuntu. Можно легко экспортировать/импортировать устройства (ovf) от них. http://www.virtualbox.org/manual/ch01.html#ovf
Вам нужен как минимум порт 53 (DNS) для UDP и TCP.
Если вам действительно нужно принудительно использовать всех через прокси, вы можете рассмотреть возможность размещения прокси напрямую между Маршрутизатор и доступ к WAN в прозрачном деле. Таким образом, вы избавляетесь от необходимости настраивать прокси-сервер на каждом клиенте, сохраняя при этом функцию прокси-сервера. И нет простого способа обойти прокси.