For the former, which was the hardest, I just kept changing up species until I found some things that would grow. When I tried a new species, I would always add some mulch or soil for enhancement. I now have perhaps 15 feature trees established to various stages and have been able to expand by mulching a more fertile area at the base of the plants in which I have started to place other plants.
For the latter, I turned the earth and removed the majority of waste, mulched the whole thing lightly, wet it down regularly, transplanted some large shade trees (which survived but basically didn't grow for about a year), then began a combined campaign of continuous stick and branch mulching and food waste (surface composting). Even though much of the ground became covered in a weed, which I removed recently, the soil is now dark, rich, and highly nutrient dense, holds moisture, and contains significant planted trees, a forest of emergent palms, and self-sprouted fruit trees and vines. The transformation took around 2 years.
I do still have three challenge areas: two small beds where the soil is depleted and gets far too much sun, and one where the soil is depleted and gets almost no water. All now have plants growing, but only one could be described as thriving.