I haven't done dual contouring before, but this seems similar to how my voxel engine works. At each voxel I store 3 values representing the x, y, and z potential displacement of the surface from that sample point. The special case of 0, 0, 0 represents an empty voxel.
When building the mesh, I use a variant of marching cubes and consider each cubic cell with 8 voxels at the corners. Any cell which has a mix of 0 and non-0 voxels will contain a surface. Any cell edge connecting a 0 and non-0 voxel will contain a vertex of the mesh, and the position of the vertex along the edge is equal to the x, y, or z displacement from the non-zero voxel. This makes it very easy to calculate the vertex locations and gives me a lot of control over the surface, but still gives a lot of surface variability.
To dig a a "hole", I set a voxel to 0,0,0, and set its neighbors associated x, y, or z displacement to a random value within a controlled range. If you want straight edges, you can also get that effect by choosing consistent displacements for the neighbors.