How to make a 'rocky' material with procedural bump?
I was able to get something pretty close to what I think you are looking for using a voronoi texture.



Here is my node setup (click to enlarge):



Here is a close up of the nodes that make the holes (there are actually two of these sets, one for the larger holes and one for the smaller ones).



The upper voronoi texture, set to cells, is sent through a less than node to "weed out" a few cells I then use that result to mask the lower voronoi, set to intensity.  If that didn't make any sense here is an image that will hopefully clarify it:




Cells voronoi texture.
Put through less than 0.4 node (converter > math) to "grab" 40% of the cells.
Used to mask intensity voronoi texture.
Color ramp node added to (mostly) eliminate the hexagons.  (Try playing with the color ramp swatches to see how this works.)


The main material is simply two of these setups with a noise texture for added roughness, all put into the bump of a grey diffuse shader.  The asteroid itself is simply an icosphere with a subsurf and two different sized displacement modifiers.

Here's the .blend: