KawaiDesu

Как я понял из текста — у вас роутер+модем. В принципе можно оставить его в той же сети, что и шлюз и не делать из шлюза NAT. Тогда на роутере-модеме выключаем всякий функционал типа DHCP и делегируем эту радость шлюзу. Таким образом шлюз должен быть gateway (как я лихо избежал каламбура) на всех машинах. Для шлюза gateway-ем будет роутер-модем.
Итого:
1) Да, по вашей схеме шлюз будет NAT-ом.
2) В принципе да, я предложил другой, тут дело вкуса, имхо. Если юзеры в настройки не лезут (типа выставить шлюзом роутер-модем руками, чтобы обойти QoS) то покатит мой, ваше побезопаснее в этом плане.
3) Выигрывает в чём? Насколько я знаю, ipfw несколько производительнее. Ну и в настройке проще.
4) Не понял
5) См. п. 2

Xubuntu. Если надо — распишу почему.

Такой вариант: многие дистры линукса идут в поставке с LiveCD, вставил и работай. Например, последние убунты сначала грузятся вживую, а потом запускают свою установку. Так вот, если LiveCD найдёт дрова на сеть, то можно, например, использовать TeamViewer.
Хотя, считаю что вариант с IP KVM наиболее элегантный.

Рекомендую забрать через лайв-сиди все нужные конфиги и ставить начисто 12.04. Я один раз, кажется, 10.04 свежеустановленную обновлял и едва-едва задел, скорее коснулся SATA кабеля в открытом корпусе. Всё, машина ушла в ребут во время обновления и запускаться отказалась. В итоге переставил.