Alternatively, average utilitarians - I suspect I am one - may just reject the very first step, in which the average quality of life goes down.

It's worth noting that this approach has problems of its own. The Stanford Encyclopedia of Philosophy on the Repugnant Conclusion:

One proposal that easily comes to mind when faced with the Repugnant Conclusion is to reject total utilitarianism in favor of a principle prescribing that the average well-being per life in a population is maximized. Average utilitarianism and total utilitarianism are extensionally equivalent in the sense that they give the same moral ranking in cases where the compared populations are of the same size. They may differ significantly in different-number cases, however. This is easily seen when the average approach is adopted in the comparison of the population outcomes in Figure 1 and Figure 2. That the average well-being is all that matters implies that no loss in average well-being can be compensated for by a gain in total well-being. Thus in Figure 1, A is preferable to Z, i.e. the Repugnant Conclusion is avoided. In Figure 2, A is preferable to A+, i.e. the Mere Addition Paradox is blocked at the very first step.

Despite these advantages, average utilitarianism has not obtained much acceptance in the philosophical literature. This is due to the fact that the principle has implications generally regarded as highly counterintuitive. For instance, the principle implies that for any population consisting of very good lives there is a better population consisting of just one person leading a life at a slightly higher level of well-being (Parfit 1984 chapter 19). More dramatically, the principle also implies that for a population consisting of just one person leading a life at a very negative level of well-being, e.g., a life of constant torture, there is another population which is better even though it contains millions of lives at just a slightly less negative level of well-being (Parfit 1984). That total well-being should not matter when we are considering lives worth ending is hard to accept. Moreover, average utilitarianism has implications very similar to the Repugnant Conclusion (see Sikora 1975; Anglin 1977).

(Unfortunately I haven't been able to find the referenced papers by Sikora and Anglin.).