Multiple internet connection at office

We have been using two separate Internet connections in our office. People will share internet connection by setting their gateways to either of these. Gateway is one of our local server through which internet is shared. So, we are using two local servers for two connections. Now problem is, if any connection is down, people have to manually change their gateways to the working connection.

How we can have multiple internet connection at office without people having to manually change their gateway settings? One of our server is windows XP and another is red hat.

Thanks in advance

EDIT
One requirement is that we need to have a server accessible via static ip