Generating random but believable digital elevation model?

You can use fractals for this: .

The upper row was generated with the fractal dimension d=2.0005 (left: elevation map, right: aspect map), the lower row with fractal dimension d=2.90 (left: elevation map, right: aspect map). I used r.surf.fractal of GRASS GIS. Then simply export the artificial DEM with r.out.gdal (or the GUI) to GeoTIFF.

You could also consider having a script that takes random part of an existing real DEM.

Here's a great resource on terrain generation algorithms and software on vterrain.org: http://vterrain.org/Elevation/Artificial/