Таки проблема решена :)
Выкладываю решение. Собственно, о нём я уже тут писал в общих словах.
Итак, имеем белый айпишник, имеем шлюз из диапазона частных сетей (типа 10.0.0.0/16 или 192.168.0.0/16), также у нас есть внутрисетевой присвоенный нам айпишник. Настройка интерфейса, смотрящего в Интернет, проста и понятна. Прописываем два айпишника в файле ipv4address, причем для белого я маску взял /32 (чтобы не плодить теоретически возможный броадкаст с нашего пк). Затем прописываем шлюз в файле ipv4route и выданные провайдером днсы в файле resolv.conf. А теперь добавляем к правилам фаерволла такое (предположим, что у нас айпишник 10.0.1.20, второй белый пусть будет 85.192.x.y, а настроечные файлы интерфейса располагаются в каталоге /etc/net/ifaces/eth1)
iptables -t nat -A POSTROUTING -o eth1 -s 10.0.1.20 ! -d 10.0.0.0/16 -j SNAT --to-source 85.192.x.y
Теперь с исходящими с сервера соединениями в интернет проблем нет.
PS Решение костыльное, конечно, но что поделать, если провайдер по-другому не может вывести тебя в Интернет с белым ip.