Ваше решение самое близкое к тому, что я хотел. Спасибо!
Только я заменил ip-диапазоны на интерфейсы
# Все пакеты c интерфейса gre0 посылать в таблицу 1000
ip rule add iif gre0 table 1000
# Все пакеты из таблицы 1000 посылать в интерфейс eth1
ip route add default dev eth1 table 1000
# И тоже самое только в другую сторону
# Все пакеты c интерфейса eth1 посылать в таблицу 1001
ip rule add iif eth1 table 1001
# Все пакеты из таблицы 1001 посылать в интерфейс gre0
ip route add default dev gre0 table 1001
И всё заработало.
Поправьте меня если я что-то сделал не так
Так NAT это всего лишь подмена IP отправителя. Я забыл уточнить, что для сервера интерфейс eth0 являлся основным, сервер должен использовать интернет от провайдера 1 (eth0 <-> роутер <-> интернет от 1 провайдера), а интерфейс eth1 нужен только для того, чтобы туда направить трафик из gre0, и ничего другого
Только я заменил ip-диапазоны на интерфейсы
И всё заработало.
Поправьте меня если я что-то сделал не так