Perlin Noise, surface deformation NOT along the normal vector
You can do this, and the results can be interesting, but they’re pretty far from looking like realistic terrain. Here’s a plane deformed with 3D simplex noise (Perlin doesn’t look significantly better):

The issue is that there’s no volume to the surface, per se, and nothing preventing it from passing through itself. Deforming it only along the normal vector mostly avoids that. For a surface that looks like terrain, with actual caves, you’ll probably need some kind of voxel system like the one described in this GPU Gems article.