If you plan to texture this, read through all the steps once before beginning. There is a UV mapping tip at the end that requires planning in advance.
Now let's get on with it...
Start with a cube, make it tall

Add a plane and fractal subdivide it

Fractal subdivide it again
This time a little more "fractally".
(If by any chance this is going to be a game asset go with a lower number of subdivisions.)

Extrude your subdivided plane to give it thickness

Set up a boolean (Optional: Subdivide the column too)
For the boolean, set the Operation to "Difference" because you're carving out of your column.
Subdivide the column (non-fractal) if you want the two meshes to be of similar density. Having a denser mesh would be better if you plan to do something like mutires sculpting on this. Having a less dense mesh would be better if this will be used as a game asset.

Apply the boolean, delete any leftover unneeded geometry
Apply the Boolean Modifier from Object Mode.
Then you can move your plane object to another layer or even delete it. After moving it you can see the subtractive boolean result.
To clean up stray geometry you don't need, select any part of those pieces in Edit Mode, press CtrlL to Select Linked geometry, then Delete (X) it.

Note that this is just a start. You can further sculpt this of course.
Bonus Tip: UV Mapping
Since your reference image has textures I will mention a texturing tip. If you plan ahead you can UV map this whole thing neatly. Booleans respect and will combine UV data.
UV unwrap your plane before you subdivide it. From the top, "Project from view (Bounds)".
UV unwrap your column before subdividing and before applying the boolean. "Smart UV Project" with an Island Margin of 0.1.
To place the fractal-subdivided UV island: Select the five flat faces of the column (may need to Select Similar (ShiftG) > "Co-Planar" if you've subdivided the column too). Invert the selection (CtrlI). In the UV/Image Editor Box Select (B) the rest of the visible vertices and scale/grab to position as desired.
An example of the sort of UV layout you can create:

Note: In the screen shot above the column was not subdivided before doing the boolean. It is a different .blend file from that of the preceding screen shots.