[El Scorpio]

Но, если файрвол настроен: Код: iptables -t nat -A PREROUTING -i eth1 -p tcp --dport 80 -j REDIRECT --to-port 3128 , то компы, которые выходят в инет с принудительным указанием HTTPS прокси, тоже будут получать этот DNS? »

Прозрачный прокси обрабатывает HTTP, потому что в файрволле существует правило, которое заворачивает трафик к порту 80 на вход прокси. Чтобы прозрачно обрабатывать HTTPS, нужно для начала прописать заворачивание для порта 443

Кстати, есть же опция ""Автоматическое определение настроек прокси"!? »

Это оочень глючная опция

Реализуемо ли такое в моем случае? DHCP на сервере нет, скажу сразу. »

Для IE это реализуется через групповую политику домена. В случае её активации IE никакие другие использовать не сможет.
FF и другие программы могут работать в режиме "использовать системные настройки"

Мне самое главное, чтобы с клиентов не могли юзать сторонние днс\прокси »

В принципе, ушлые пользователи могут перенастроить FF и другие программы. Однако можно просто настроить файрволл на блокирование любых исходящих подключений.
Или сделать прокси-сервер отдельным компьютером, а на шлюзе запретить любой исходящий трафик, кроме как с адреса прокси-сервера.

UPD.
Забыл, что речь идёт про Linux, а не про Windows
Для автоматической настройки прокси можно написать скрипт, который будет записывать нужные значения в конфиги системы и пользователей