How can I upgrade router on a stick redundancy?

Each router interface has a unique broadcast domain(or domains if subinterfaces used). Each VLAN is in it's own unique broadcast domain. So it would seem that you could add a separate VLAN and route it to a new IP address on a different router interface for redundancy. However, if different hosts have different default gateways to get to the same router and one of the lines goes down, the hosts that are on the default gateway still up would be working fine but for the other hosts they would need to route their packets to the default gateway in order for them to communicate with the other VLAN whose line is still up and since their default gateway is down I don't see how this could work. It would seem that you are looking for an etherchannel for routers which I don't know of.