Exploding a solid object
The cell fracture addon creates solid pieces to match the volume of the selected object. If you have failed trying the cell fracture addon you may have missed that it leaves your object intact and places all the new pieces onto the next layer, you need to change layers to see the pieces.



After enabling the addon, there is a cell fracture button added to the tools region but you may find it easier to press space and type in cell. For a simple cube you will either want to subdivide multiple times or add a particle system then run the addon.



This blender cookie tutorial covers the cell fracture addon.