It is not something that I (or I suspect anyone) will want to re-derive in this limited space here.
Letting $E$ be the fundamental solution: $P(D)E = \delta$.
In the case $f$ is $C^\infty_0$, we obviously have a distributional solution by taking a simple convolution $u = E * f$.
In the case $f$ is a distribution with compact support, the same holds true: the distributional convolution $E*f$ is also well defined, and that it is a theorem (see equation (4.2.5)' in ALPDO v.1) $P(D) E*f = (P(D)E)*f = \delta * f = f$.
For the general case where $f$ is a distribution (an element of $(C^\infty_0)'$), one has to be more careful, and the discussion is nontrivial. One cannot just simplemindedly take the convolution, since convolutions of two arbitrary distributions may not be well-defined (and may not satisfy the expected properties). Sections 10.4 through 10.8 of ALDPO v. 2 is devoted to demonstrating that indeed, the equation $P(D)u = f$ can be solved for $f \in C^\infty_0(X)'$ when $X\subset\mathbb{R}^n$ is an open subset that is $P$-convex for singular support. (In particular, any convex open set is $P$-convex for singular support.)
The proof given in ALPDO is non-constructive: it passes through the Hahn-Banach theorem to show that $P(D)$ induces a mapping $C_0^\infty(X)' \to C_0^\infty(X)' / C^\infty(X)$ that is surjective. Essentially one "solves" the "singular part" of the equation first, and leaving a smooth part. The $P$-convexity property is used to solve this singular part. The smooth part can be corrected for using the linearity of the operator and the fact that $P(D)$ can be inverted over smooth functions (another nontrivial theorem proven earlier; its proof depends on knowing the regularity properties of the fundamental solution $E$).
To summarise: while it is true that Malgrange-Ehrenpreis can be used to derive the solvability of $P(D)u = f$, there are quite a lot more quantitative information one needs to get (from various sharper forms of the Malgrange-Ehrenpreis theorem) before one can deduce the claim that $P(D)u = f$ is solvable for any distribution $f$. If you really want to see how the proof works, and assuming you have a working knowledge of distribution theory, you should read Chapters 7 and 10 of ALDPO.
ALPDO stands for Analysis of Linear Partial Differential Operators by Lars Hörmander.