Note: This topic is way too large to be answered appropriately in a StackExchange answer. You will have to do your own further research / googling.
Fundamentally, you're trying to figure out a representation of a voxel grid. The simplest possible way to represent a 3D grid is a simple array, like
map = new Voxel[width, height, depth], where Voxel is some kind of small structure that represents the material at a particular point, e.g. air, ground, water, etc. However, this wastes a lot of space on possibly empty or uniformly solid areas. The storage required is roughly O(N3). Finding a way to cut that down leads us to.....
Space Partitioning Structures
To overcome the storage shortcomings of a dense voxel array, you would look into a space-partitioning structure (such as a quadtree, octree, spatial hash, etc.) The primary advantages that all these structures satisfy are:
Sub-linear retrieval time of the volume data at a particular coordinate. (The trees will have O(log N) and the hashmap should have O(1)). There will be some differences between the structures, such as the trees are scale-invariant and so are suitable for large-scale LOD operations.
No space wasted on large empty (or possibly uniform) areas.
Typically for performance reasons, the leaf nodes of this structure will be chunks of voxels that represent, for example, an 16x16x16 volume.
One misconception in the question is that a quadtree would not be able to handle overhangs. This is not necessarily true. Even in a hash-table, a hash collision does not actually lose data. There are multiple ways of handling overlap. For example, Minecraft uses a quadtree, since its vertical-axis is limited to 256 units, which is small enough that its chunks are simply 16x16x256 columns.
We now have a data structure where, generally speaking, we can query for data like
Voxel v = myGridStructure.GetVoxelAt(100,100,0);
How do we translate this into a triangular mesh that the graphics card can render?
The simplest way, (i.e. the Minecraft method), is to generate a square at every boundary between "air" and "not-air". This yields a blocky look that a lot of current "voxel games" use. There are many other algorithms out there that attempt to generate a smoother surface. The classic algorithm is called Marching Cubes, but there are also other algorithms such as surface nets(almost a smoothed naive algorithm) or dual contouring (requires a gradient vector, but gives nice sharp edges). This page is one of the first Google matches for isosurface extraction and links to some papers on the topic.