On the derivative paradox.
I think it is essential to raise doubt in the students' minds about what the OP's calls "the derivative paradox," at least in the case of instantaneous velocity, which is what I use to introduce the derivative. I've related before the story of a friend of mine who got a fortune cookie whose fortune read, "Never try to prove what no one doubts." The doubt motivates whatever technical move is needed, whether for a theorem, its proof, or a definition, such as using a limit to not let the denominator reach zero, as Will Orrick observed.
No student fails to grasp the paradox, and part of that paradox is the feeling that there must be such a thing as instantaneous velocity.
"Everyone has or believes to have an idea of velocity," said Lagrange in criticizing one of the two common approaches to analysis at the time. Indeed, most textbooks (that I've read) omit the paradox and latch directly onto our intution:
"The idea of instantaneous velocity makes intuitive sense, but care is required to define it precisely." (Rogawski/Adams/Franzosa)
"We assume from watching the speedometer that the car has a definite velocity at each moment, but how is the 'instantaneous' velocity defined?" (Stewart/Clegg/Saleem) Not only do they assume it exists, they implicitly assume it is the limit of the average velocity: "...[W]e can approximate the desired quantity by computing the average velocity over the brief time interval of a tenth of a second..." (Stewart/Clegg/Saleem). In similar fashion, it is common to assume the slope of the secant line approximates the slope of the tangent line, without any prior definition of tangency. It seems fine to me to make such assumptions. Textbooks, and therefore I assume many teachers, make plenty of them in teaching first-time calculus, just as I do. I have two criticisms. One is what are being assumed, defined, and proved should be made clear. Many of the textbooks are so informal at the beginning (introduction) of the calculus that it is sometimes vague which of the three is happening with regard to instantaneous velocity and the slope of the tangent line. The other criticism is that if the idea of instantaneous velocity makes clear, intuitive sense, I wonder why it took so long to define it precisely. That is a long and interesting investigation, which I won't go into, but the point is that there is a paradox like the OP's which cannot easily be dismissed as being intuitively obvious. As others have pointed out, it is the definition of the derivative that is meant to get the student past the paradox.
This Q&A came to my attention because of the update by the OP that included a sad assessment, "Everything I thought might be a problem ended up as a non-issue because no-one challenged anything."
Ever since graduate school, when the younger sister of one my students said hi to me when we were introduced by saying, "Math is bogus!," I have encountered such attitudes. And I have always taken seriously their reactions. I think their attitude toward math contributes to the student's feeling that challenging anything in math is pointless. I teach in the US, and, of course, not every student has the same experience. The OP mentions "A level," which I take to mean they are working within the British educational system or one based on it. I do not know what difference that makes, though. I know that students might leave my class with a math-is-bogus attitude, despite my attempts to show them true, non-bogus mathematics, because they come into the course with preconceived notions and bogus math feels comfortable when they are good at getting right answers.
What I have to share here is a different approach that complements other answers. Certainly I think the derivative paradox is handled adequately by the definition of the limit. However, I think we can do better.
A rich understanding of mathematics comprises more than the logical structure created by our choices of axioms and definitions.
The connections that motivate our choices are important.
As Proclus said, "...mathematics, though beginning with reminders from the outside world, ends with ideas that it has within...."
Often what motivates our choices becomes clear only on reflection, after we try out a definition and see why it succeeds. I offer an approach to derivatives motivated by an intuition that what we would like is for the average velocity of a smoothly moving object to vary continuously.
An approach to the derivative paradox
Does anyone have any ideas, experience-backed, for how to take a curious student past the “derivative paradox”?
Perhaps you will like the following approach, which I adapted from Stephen Kuhn (The Derivative à la Carathéodory. Am. Math. Monthly, 1991) after seeing Ray Mayer's notes for Math 112 at Reed College. I chose a slight twist to Kuhn's idea. Kuhn's small observation that the average rate of change between a variable point $x$ and fixed point $c$ can be extended to a continous function at $c$, in the case where $f$ is differentiable at $c$, is key to the kind of model of change we want to create in calculus/analysis. Our experience of the real world leads us to imagine that in continuous change, such as we experience in observing the motion of an object, velocity changes continously when an object moves smoothly. Treat these observations as intuitions, and ask, how can I create a mathematics that models what I imagine I see? Once we create such a mathematics, we can analyze which functions model smooth change and which do not.
Building on our notion of average velocity or rate of change, the change in position over the change in time, there is a fairly clear way to procede, as set out by Carathéodory (Theory of Functions of a Complex Variable, AMS/Chelsea, 2001; orig. 1954; German ed. 1950).
We may define differentiability and the derivative as follows:
Given a function $f$ defined in an open interval containing a given number $c$, if we can find a function $f^\Delta$ such that (1) $f^\Delta(x) = [f(x)-f(c)]/(x-c)$ for all $x\ne c$ in the interval
and (2) $f^\Delta$ is continuous at $c$, then $f$ is said to be differentiable at $c$ and the derivative of $f$ at $c$ is given by $f'(c)=f^\Delta(c)$.
Example 1 (differentiability).
Let $f(x) = x^2$. Fix a number $c$ (any real number).
Then $[f(x)-f(c)]/(x-c) = (x^2-c^2)/(x-c)=x+c$. Now, $f^\Delta$ defined by $f^\Delta(x)=x+c$ is continuous at $c$, and it is equal to the average rate of change of $f(x)$ for $x \ne c$. Hence we have found the required function, and therefore $f'(c)=2c$.
Note that the algebraic mechanics of finding $f^\Delta(x)$ is the same as finding the limit in the limit formulation of the derivative. Indeed, it is easy to prove they are equivalent. OTOH, the conceptual goal is to find a continuous model for the average rate of change in a neighborhood of $c$. At no time are we concerned with a limit of the indeterminate form $0/0$.
Discussion.
The process works this way for the standard algebraic examples used to introduce the derivative. I think that is sufficient to recommend it. In terms of mechanical algebraic operations, there is not much difference, which may leave you thinking that the difference is negligible. I might add that the "recipe" is to start with the average rate and analyze. For an algebraic function, factor out $x-c$ and reduce to a continuous function. I like that we focus the discussion on the average rate and the question of its continuity instead of on a limit formula.
(When working from the limit definition of the derivative, one could structure the limit computation to start with the average rate, but it seems natural to start with the formula given in the definition.)
See Example 4 below for a transcendental function example.
I do like to give an example of nondifferentiability, not only because it is good practice to show objects on both sides of the boundary drawn by a definition, but because of how it reflects on the goal of finding a continuous model for the average rate of change; see Example 4.
First, Example 1 may be extended as follows.
Example 2 (mutatis mutandis).
Let $f(x) = x^n$ for an integer $n>2$.
Fix a number $c$ (any real number).
Then $[f(x)-f(c)]/(x-c) = (x^n-c^n)/(x-c)=x^{n-1}+c\,x^{n-2}+\cdots+c^{n-1}$, a polynomial.
Now, $f^\Delta$ defined by this polynomial is continuous at $c$, and it is equal to the average rate of change of $f(x)$ for $x \ne c$.
Hence we have found the required function, and therefore $f'(c)=n\,c^{n-1}$, the value of the polynomial at $x=c$.
Example 3 (general rule).
Let $f^\Delta$ and $g^\Delta$ be the continuous extensions of the average rates of change of functions $f$ and $g$ respectively, assumed to be differentiable at a number $c$. Then it's easy to show $f^\Delta+g^\Delta$ is the required "Delta" function to show the differentiability of $f+g$ at $c$. Exercise left for the reader.
Example 4 (singularity).
Suppose a ball bounces off a wall,
such that the ball initially had some constant velocity, say $v$,
and after the bounce the velocity was constant but $-v$.
The position would be given by $f(t)=-v\,|t-c|$,
if we set the time of the collision to be at $t=c$.
The average velocity between $t$ and $c$ is
$$
\cases{\phantom{-}v & if $t<c$; \cr -v & if $t>c$. \cr}
$$
Since the limit as $t \rightarrow c$ does not exist,
there can be no function $f^\Delta(t)$ that is continuous at $c$
and equal to the average velocity for $t \ne c$.
Thus the position is not a differentiable function at $c$,
and we do not have a way to define the derivative at $c$.
Discussion.
One might argue that the average of the two velocities, a velocity of $0$, makes sense as a way to define the derivative since the wall is at rest and the ball is in contact with the wall at $t=c$.
(Compare with the central difference formula.)
But looking to the physics in this case is problematic, since rebounds are quite complicated phenomena that are not instantaneous. To rely on the physics requires a more complicated and reliable model than the absolute value. To refocus our attention, it is the nondifferentiability of the absolute value that is our interest.
We may like to imagine that velocity is an inherent property of an object, like its color, and present at each instant.
As far as our model of an instantaneous bounce goes,
it's probably best to say the instantaneous velocity at $t=c$ is undefined.
Note that this conclusion is about our model and not about the physics of bouncing; however, the nondifferentiability of absolute value is a consequence of our choice to base differentiability on extending the average rate of change to a continuous function.
Viewing differentiability as the continuity of the average rate adds some interest to the standard pathological example $g(x) = x^2 \sin(1/x)$ for $x \ne 0$, $g(0)=0$. For any $c$, there is a continuous $g^\Delta(x)$ that equals $[g(x)-g(c)]/(x-c)$ for $x \ne c$ — continuous, as it turns out, for all $x$. So $g'(c)$ is defined for all $c$. But despite the continuity of $g^\Delta(x)$ for each $c$, $g'$ is not itself continuous at $0$. Later one can spiral back to take up the continuity of $g^\Delta$ as a function of $x$ and $c$ in multivariable calculus.
Remark on $\sin x$ and friends.
Once you get past the introduction of the idea of a derivative, one can simply use the limit formulation of the derivative to find the value for $f'(c)$ at the missing point $x=c$ that makes the average rate continuous at $c$ (or show no such value exists).
But if you want to continue with the approach in example 1, the transcendental functions offer challenges that are familiar when using the limit formula. The two processes never need be very different, after all.
Example 5.
So for $\sin x$, one can show geometrically that if $x$, $c$ lie in the same quadrant, $\sin x - \sin c$ lies between $\cos x\cdot (x-c)$ and $\cos c \cdot (x-c)$. One can use the squeeze theorem then to show $\cos c$ extends $[\sin x - \sin c]/(x-c)$ to a continuous function at $c$.