StackOverflow eventually reminds me of this question existence, so I'll take some minutes to answer how I solved it.
I guess it's not possible to replace a running JSF webapp without view state related exceptions if the page structure that the user was accessing changed somehow.
I was able to perfectly solve this using Tomcat's parallel deployment, where older versions of the webapp stay on the server until they have active sessions.