If you have two tomcat's running in a cluster (behind a load balancer or behind apache), it's really easy.
- Take server 1 out of the cluster, update server it.
- Bring server 1 back up.
- Take server 2 out of the cluster, update server it.
- Bring server 2 back up.
Anything else will result in downtime (however brief) if you're doing a full redeployment of your application.
If you can tolerate a small bit of downtime (<1 sec), then you can emulate this by deploying to a second instance of tomcat, then point your load balancer to the second instance. In this case, you will lose any active sessions, but the switch should be real fast.
In both cases there are database synchronization issues that you will have to address though.