заставить машины ходить через прокси

Ищи описание прозрачного прокси.

Под внешней проксёй я имел ввиду не мой фаервол. Т.е. это уже существующая прокся, чужая.

"Можно ли настроить фаервол..." Я так понимаю, что фаревол ты можешь настроить? Если нет, тогда непонятно чего ты хочешь.

Да как обычно - если твой файрволл имеет инет через проксю, то твои машины автоматически через нее выйдут.

Читай руководство по iptables, чтобы понимать как пакеты ходят (ссылку возьми в faq в разделе network).

P.S. Внимательно посмотри на цепочки input/output и сделай на те же порты проброс с forward.

Есть такая штука - transproxy называется (http://transproxy.sourceforge.net). Это маленькое чудо умеет переписывать запросы так, что они идут через внешний http proxy. Лично я не пробовал, но по идее должен быть не тяжелым. В документации как пользоваться написано вполне понятно :)