Normal map generation - shaders and FBO

Question

I want to generate a normal map from a heightmap. I know it's a pretty 'overasked question', but I haven't found any good topics about this. The normal map should be about 6-8x larger than the original texture. I've implemented it on CPU, but this is pretty slow for a big texture, instead of it I want to do it with shaders. My idea is to render the height map to a full screen quad, and with shaders I turn it onto a normal map in fragment shader, then save the FBO texture. This could be done during init. of the map. But how can I render it with any resolution?

Lets assume the heightmap is *20,000*20,000*, then the normal map should be 160,000 * 160,000. That's more than 25Mrd texels. For sure I would only stream a part of it to the GPU. Does the resolution of the normal map depend on the viewport or the max resolution my GPU supports, or I can make very big resolution textures?

Is there any way of creating VERY big resolution textures on the GPU using shaders? Now I'm calculating the normals every frame in the terrain shaders with bicubic filtering, this is extremely smooth, but since it's static mesh, it's not necessary, and also affects the performance badly.

My algorithm is to get the interpolated height, then sample 4 more around the specified height. Then a simple corss product:

h(x,y) //is samples 16 heigths, then interpolates them using bicubic filtering
n(x,y)
{
    h1 = h(x+offset0,y+offset0);
    ...
    v1 = (x+offset0,h1,y+offset0)
    ...
    c1 = cross(v1-v0,v2-v0)
    ...
    n = normalize(c1+c2+c3+c4)
}

This needs 5 * 16 = 80 samples per normal. 25,000,000,000 * 80 = 2,000,000,000,000 texelFetch for my normal map. That's seems a very big number for me, I have only made a normal map for a 4000*4000 heightmap yet (on CPU), but that was pretty slow. About how much time would it take to compute it all? On the GPU this would take ~5 minutes I think. On the CPU...I won't try.

Do I get the same results with linear filtered heightmap lookups, then run a bicubic filter on the normal map in the end?

I can't use a 3rd party software for this generation, I have to implement it myself using OpenGL. If it's depend on the GPU to make big resolution maps, maybe I could render a part of the normal map once, then the others.