g1smd - 6:30 am on Jul 16, 2013 (gmt 0)
All four of your proposed solutions have merit, merely differing by the amount of work involved. I would certainly keep the old pages active to begin with and monitor traffic before deciding whether to retain or redirect.
I am hoping that your product URLs do not contain category folder levels. If your product URLs don't contain category folder levels, you can alter the categories without affecting the product URLs.