It seems to me you could just start at the upper-left corner and add offsets calculated from the normal map values as you move right and down. Just the opposite of the way normal maps are calculated from height maps (by taking differences between adjacent elements).
You would want to do it in floating point, keeping track of the maximum and minimum height reached, and then scale to [0, 255] range when done.
I don't know how accurate this would be at reproducing the original height map. Might take some tweaking.