Minerals:
For a tree to deposit a stone core, all you need is minerals to be present in your environment in such quantity that they can be treated like a waste product. Look to coral, or sea shells, and imagine a plant depositing the same stuff. Fossilization can take very long or almost no time at all, if the appropriate dissolved minerals are present in the water.
I imagine trees eating away at limestone deposits, then depositing the carbonates in structural columns inside the tree. The stuff might be effectively a waste product, but a useful one. The tree is essentially filling the inside space with lime deposits, and protecting the lime deposits with the outside of the tree. The tree could be reclaiming the wood it laid down and replacing the lost structural material with what is essentially limestone.
This is an easy stone to work, very porous, and the tree may even leave natural cavities in the structure. This could aid in ease of tunneling. Limestone is used as a building material and ingredient in cement. As long as the outside of the trunk is alive, the inside is protected. The minerals soaking down would likely cause interesting deposits in caves people made, giving it a very organic feel. I've even seen basements in limestone that were growing crystal-like structures and had opalescent deposits.
The ability to transport materials is often the limiting factor on how high your trees can get. If you can have a natural way to pump the material up, though, the sky is literally the limit. How do geysers sound? These have (admittedly dangerously) hot, mineral-soaked water under pressure that the tree could direct upward in narrow tubes to fill a pool at the top. The water and minerals are soaked downward to make the tree and supply needed water and minerals (as well as the structural minerals for your exotic growth). The trees that grow near geysers become enormous, while the trees simply drawing on water in deep limestone deposits are "merely" huge. There could even be different varieties, and people carry geyser-type plants to geologically active areas and spread the species.
That gives you giant trees, symbiosis between man and tree, and geysers (what story isn't better with hot running water?) There could be a lot of different complications with this design that need to be hammered out, but unless someone has a huge and obvious objection, I think this could be a viable route for you.