There are at least two other decomposition that (I would argue) have been the foundation for fundamental advances in harmonic analysis.
(1) The wave packet decomposition. This decomposition underlies the proof of Carleson's theorem (this is more explicit in Fefferman's proof than Carelson's original proof), Lacey and Thiele's proof of the boundedness of the bilinear Hilbert transform, as well as a host of follow-up work in multilinear harmonic analysis. The idea of the wave packet decomposition is to decompose a function/operator in terms of an overdetermined basis. This allows one to preserve symmetries (such as modulation symmetries) that aren't preserved by a classical Calderon-Zygmund decomposition (which endows the $0$ frequency with a distinguished role). One might consider using a wave packet decomposition if is working with an operator that has a modulation symmetry. This is discussed in more detailed in Tao's blog post on the trilinear Hilbert transform.
(2) The polynomial decomposition. The application of polynomial decomposition to harmonic analysis is more recent, and its full potential still seems unclear. Applications include Dvir's proof of the finite field Kakeya conjecture, Guth's proof of the endpoint multilinear Kakeya conjecture (and, indirectly, the Bourgain-Guth restriction theorems), Katz and Guth's proof of the joints problem and Erdos distance problem, among many other results. Generally, the idea behind the polynomial decomposition is to partition a subset of a vector space over a field into a finite number of cells each of which contains roughly the same fraction of the original set. One further wishes that no low degree algebraic variety can intersect too many of the cells. In Euclidean space, the polynomial ham sandwich decomposition does exactly this. This allows one to, for instance, control linear (or, more generally, `low algebraic degree') interactions between points in distinct cells. This has so far proven the most useful in incidence-type problems, but many problems in harmonic analysis, thanks to the translation symmetry of the Fourier transform, are inextricably linked with such incidence-type problems. See (again) Tao's survey of this topic for a more detailed account.