Из самого очевидного:
1. Выбрать 2 ip в инете, которые будут пинговаться для определения доступности, для каждого канала по одному адресу.
2. Прописать статические маршруты до каждого из выбранных ip, через соответствующего провайдера. Т.е. адреса должны пинговаться без прописанного шлюза по умолчанию (default) причём каждый из них через свой канал провайдера.
3. Далее, задача сводится к установке default gw на основной или резервный канал, в зависимости от результатов пингов. Причём, для корректной работы nat, желательно при переключении канала зачищать уже открытые соединения nat.