I'm skeptical Knuth's scheme will be much of an improvement.
I think the problem with teaching any kind of rigorous definition of limits or derivatives to the vast majority of North American students isn't going to go away by streamlining the proofs a bit.
The problem isn't the technical difficulty of the proofs so much as the idea of proof itself, and even the idea of working from precise definitions. Students have nothing that prepares them for this in their background, because from elementary school all through high school the idea of justifying statements is treated as unimportant. This is true even when the justification would be simple, such as for the rule $\log AB = \log A + \log B$. I've taught from textbooks where the authors ease their consciences by having a page titled "Proofs in Mathematics" at the end of each chapter, as if mathematics without proofs could have any meaning.
As for the technical merits of having a long discussion of $O$ notation as a prelude, let me first say that Knuth misstates things slightly. $O(f(x))$ would have to be defined as a function that is $CA(f(x))$ for some constant $C$ on some $x$-interval around the point of interest. Perhaps this is what he means when he later says "for $\epsilon$ sufficiently small." In any case, that introduces the dependence on the variable $x$, which makes this concept not much easier than defining the statement $\lim_{h \to 0} g(h) = 0$ (which itself leads directly to the definition of finite limits in general, by the condition $\lim_{h \to 0} [g(h)- l] = 0$).
And even if one were to present rigorous proofs of the laws on strong derivatives, is this really better than the traditional proofs using the limit laws? Students always find the limit laws very plausible, and once those are accepted, then the proofs of the differentiation laws become accessible, and can be particularly convincing if you write $\Delta x$ for $x - a$, $y$ for $f(x)$ and $\Delta y$ for $f(x) - f(a)$. The proofs of the differentiation laws might become more rigorous in Knuth's scheme, but I am inclined to believe that they would also be made considerably less transparent.
Ultimately, presenting proofs that are meaningful to students at their level of understanding will do more to foster a healthy respect for the idea of proof than will giving proofs that are technically irreproachable but too demanding technically. I also believe the few students who could handle the $O$-proofs would probably manage with the traditional rigorous approach anyway.
If there is any advantage to Knuth's method, it might be that of avoiding discussion of limits early in a calculus course, when you would otherwise bore students with things that seem pointless to them, like $\lim_{x \to 3} (x^2 + 5x) = 24$. You derive these results at first using the limit laws, though every example they see at first is obtained by simply substituting a value of $x$ in the expression (perhaps after simplification).
But limits need to be dealt with eventually; statements such as $\lim_{x \to 0} \frac{\sin x}{x} = 1$ or $\lim_{x \to +\infty} \frac{\ln x}{x} = 0$ are intrinsically interesting and necessary.
The real problem with limits is how to teach them in such a way that students will understand from the start that there's more to them than just substituting a value in.
The answer is probably to de-emphasize limits initially by treating them very briefly, with few exercises on them, developing only enough technical proficiency to accurately compute derivatives of rational functions, computed as limits of the form $\lim_{h \to 0} \frac{1}{h}[R(x+h) - R(x)]$, and without requiring much theory to be understood. Then return to limits when it is time to talk about less trivial ones, after they have already seen the usefulness of the concept demonstrated in the theory of derivatives. The meaning of the limit laws becomes much easier to grasp when they are used in a way that is not obvious. Continuity can be postponed until this point as well.
