This sounds difficult, without making a new instance.
I just tried the "shader-method" in the editor. UVs (or other shader parameters) only works inidividually when the mesh is a new instance (= "make unique" in the editor) and the material is a new instance ("make unique" again). So just the shader stays the same (parametrized via the materials parameters).
Back to your last question. Yes, you should be able to to change the UV-Mapping in a mesh. This should be possible via the MeshDataTool with the method setvertexuv2. (You init an Instance of MeshDataTool with the method createfromsurface. You get the mesh with get_mesh() from the MeshInstance.
If you change the mesh, then it would be for every node which uses the same instance.
I think that you HAVE to have an own instance for each mesh which is animated individually. Personally, I see no other possibility. But perhaps someone else has a better idea...