How to animate noise texture "seed"?
You can not animate the seed of a 3D gradient noise texture because it´s usually all fixed in a permutation table. What you are basically looking for are 4D gradient noise textures.

Why do 3D gradient noise textures not work? Imagine a 3D procedural texture as a continuous grid in space containing colour or intensity values at any node. Also imagine your mesh inside this grid. For simplicity imagine that every point on the surface of the mesh gets the colour of the nearest point of the grid assigned to it. Now imagine moving the grid or the manifold mesh. Eventually the points will move along the normal of a few faces but they can usually not move along the normals of all faces at a given time. And if they don´t move perfectly along a normal they will slide along the surface.

To overcome this limitation we need to add a dimension which we can then animate.

So how can we do this in blender/cycles? 

We can program it ourselves in OSL(Open Shading Language). First we need the code for our 4D texture shader (e.g. a very simple one):

#include "stdosl.h"

shader simple_noise_texture4d(
float Scale = 1.0,
float Time = 0.0,
output color Color = 0.0
)
{
    Color = noise( "uperlin", P * Scale, Time );
}


Use the internal text editor and name the above text block e.g. noise.osl. We use the builtin noise function with 4D unsigned perlin noise. The 4th component named Time will be used to animate the texture. Scale is used to scale the texture as usual. The output is named Color. For more information see the OSL specification osl-languagespec.pdf. 

Edit: By the way, there already exists a script template "Noise" in the text editor called noise.osl. I didn´t know this by the time I posted this answer. It provides some more 4D noise algorithms.

Important

On the render tab of the properties panel enable "Open Shading Language". The Open Shading Language checkbox will only be available with CPU render mode.

Then add a material to the object as usual and add a script node and set the shader script to "noise.osl". Click the "Update shader.." button next to the shader name input. Use the output colour e.g. as input colour for a Diffuse BSDF shader. 



Now Time can be animated as usual.



For more complex noise just edit the OSL code accordingly.