Another idea: procedurally generate an image (perlin noise, etc.) and use vertex texture fetching to deform the mesh? This way the image could be changed and the mesh updated...

But this is still not really a procedural terrain :P