Efficient method of doing runtime updates on a model?

I'm trying to implement some procedural generation algorithms using OpenGL, and I want to be able to control how many "layers" I'm putting on top each time. I initially planned to put the vertices on a square lattice and starting as a flat plane, then increase the height of a random vertex (chosen at random) by one.

However, as far as I can tell the vertices have to all be declared before runtime, so this would require a massive number of vertices from the start (e.g. a square alone would require 4), and this would lead to a lot of redundant vertices for flat surfaces. Is there a better way to implement this?