How about this:
On the left, the mesh inside out with one of the interior spaces selected. The middle one is the unsmoothed rock, and the right one is the same thing with a Subdivision modifier attached.
Here's the
Cheetah3D file for closer inspection.
I didn't spend much time making it look rocky, since it's the principle that's most important in this case. You can follow Frank's advice for the visual quality side of things.
I made it by starting off with a cube (as I do for most things), then subdividing the polygons to get a roughly round shape, and stretching it out a bit. In polygon mode, I selected groups of polygons and extruded them inwards, then used the Normal Scale tool to taper them a bit. This makes some initial craters. You can fiddle with this in all sorts of ways to make it look more organic, but the trick is to avoid having too many polygons... keep it simple, and subdivide it at the last step to smooth it out (don't do that just yet!).
OK, so you've got a rock with craters now. To make the tunnels and interior spaces, you need to extrude some of the craters in even further. Of course, you can't see what you're doing if you try to work on the inside of the rock, so you should use Flip Normal on all the polygons to turn the object inside out, and turn on Backface Culling to hide the outside of the rock. Don't forget, with Backface Culling on, you can only select the side of the polygon that's visible, so turn the model around to look right through the asteroid at the back of the faces you want to work on.
Now just keep extruding the underside of the craters to form tunnels and rooms. As you extrude, you can rotate and scale the leading edge of the tunnel to make it point in a different direction for the next step of the extrusion, and you can just drag stuff around to make tunnels into larger spaces. Again, remember to keep things comparatively simple; you can subdivide it later.
If you want to make your tunnels join together to form a network, you'll need to use the Bridge tool. Delete a face on each of the tunnels you want to join, and use the Bridge tool to link them together. You can also add extra detail to the bridge tunnels by using the Ring Cut tool to add extra segments, then reshaping them.
Once you're done, flip all the normals back the right way around, then apply subdivision to the object.
Hope this helps. Let me know if you need more clarification.
