I'm working on a Worms-styled game and want to generate some terrain procedurally. I've previously done a lot of terrain generation using perlin noise, and this is what I started out using for this game. The only problem with it is that it's too simple and boring, giving me some hills but not the complexity I want. I'd like to have features like caves and hanging mountains and I don't mind floating islands and such. Something like this, but even crazier would be ok:
I thought of first generating the terrain using classic perlin noise, then just removing parts to create caves and what not, but I'm having trouble guiding the removal of those parts. Are there any alternatives to generating such a terrain?