tldr: a holding attribute just means that, if the code is reasonable, the evaluation is non-standard, but doesn't mean there's no evaluation.
HoldAll and his holding friends only mean there is no automatic guaranteed standard evaluation taking place. Evaluation might still happen if it was manually coded that way. For example
f[x_] := Hold[Evaluate[x]];
This would be unreasonable code, sure: why would you give
f a holding attribute only to force it to evaluate as usual? BUT, possible.
In the case of
SetDelayed and others, the evaluation that happens isn't the standard one. For example, after doing
x[]=4; should not evaluate to
2=4. After doing
g[x_] := x^2;, running
g:=6; should not evaluate to
4:=6. But heads and arguments, when the left hand side is of the form
_[___], are. This non-standard evaluations can only be achieved by turning automatic evaluation off and then evaluating what you want by hand.