A lot of this depends on whether you are doing any session/state management on the Tomcats. If a user's session is destroyed by the restart, then rolling doesn't prevent user impact (it might prevent them from seeing a 500, but not from having to start their session over). If you're not using sticky sessions than you probably don't have to worry about that.
HAproxy, and other load balancers, have ways to try to pretty quickly determine if the server behind it is up or down and reroute traffic based on that (the "health check," in HAProxy). It is impossible for them to do that perfectly, however. With Tomcat, there isn't just "up" and "down"; there's "up, as in responding on the port, but things aren't ready yet". So you shouldn't rely on the LB to completely prevent user facing impact - even with a good health check there will be an interval where you're getting traffic to a bad node.
What we do with a rolling deploy is to actively take the server out of the load balancer, then mess with/restart the node, wait till it passes an automated test/monitor, then put it back in, then move to the next server. This is easier with a load balancer that has an API you can call remotely (like, from a script) to disable a server - our old Netscaler did this, but HAProxy doesn't. With HAProxy you either have to edit config and restart (sad) or you can change the health check to where you can manipulate it - like maybe it checks a magic file you rename when you want it to omit that node. You have to wait for the health check to fire and the node to go out of the cluster, but then you should be fine.
I ran across this post that has a iptables-related solution to that problem...