Actually you could do it the exact same way as a tax table change, for time period X everybody’s tax table would land at zero. Not that tough at all.
Try it. The software doesn't expect zeros in many cases. It has a bottom level that doesn't get taxed, but that is sometimes hard coded.
I am in this business -- I wouldn't sign on for doing it in under a year. if you haven't implemented systems in a loarge scale or dealt with home grown systems with 100,000+ employees or more, your opinion is just an uneducated guess.