You could generate, analyse and discard random noise fields.
Just generate thousands of them, and keep the ones that have a fully enclosing wall on the outside.
For generation, I would use Simplex Noise. Here is my implementation in C for it.
After generating a 2D field with values in range [-1,1], you pick a threshold value (let's assume 0.0) and define WALL as > 0 and VOID as <= 0.
Then you test the entire rim (x==0 || x==max || y==0 || y==max) for being WALL. If one value on the rim is not WALL, discard this cave, and generate a new one with different noise coordinates.
You can put more restrictions on it too, as: no disconnect of the cavity. To test this, floodfill from a void sample. If the set does not contain all void values, then the void is disconnected, and could be discarded.
For a little more efficiency, you could also dynamically pick the threshold value by setting it to the lowest value found on the rim. This way, a closed rim is guaranteed. (Note that you can also guarantee this using Sean's suggestion of scaling the values based on distance to the centre.)
And then examine the cave. If it is too small, or disconnected, continue to the next random field.
But the key point I am trying to make here: you don't have to specifically force your generator to satisfy constraints, it is enough if you can analyse and identify these constraints after which your filter your solution.