изменение таблицы маршрутизации при помощи icmp

Надеюсь что нельзя.
На сколько я понимаю пятый тип ICMP предназначен не для внесения изменений в таблицу маршрутизации, а для перенаправления отдельных пакетов.

на удалённом компьютере

Как я понял, «новый» шлюз должен быть в одной подсети с источником.

Если можно то как?

Очевидно, что сформировав и отправив icmp пакет нужному хосту. Хотя, не факт, что хост послушается.

$ sysctl net.ipv4.conf.all.accept_redirects
net.ipv4.conf.all.accept_redirects = 0

Очевидно, что сформировав и отправив icmp пакет нужному хосту.

В этом то и вопрос, как сформировать.

Хотя, не факт, что хост послушается.

Это понятно, можно просто 5 тип icmp на сетевом фильтре закрыть.