There is no generic solution for this problem: The same menu can be rendered with different walkers on different pages, or plugins change the menu on some pages.
You could extend your script to evaluate the differences to an untouched menu and build the necessary JavaScript on the fly … and cache that too … for each single page.
I don’t think it is worth the hassle. getting all the edge cases right is hard work, and the menu would still be different for users without JavaScript (search engines, unresolved script errors etc.).