average utilitarianism [...] killing off anyone with below-maximum utility is an improvement.
This is true insofar as it can be performed without creating significant disutility for their above-average-utility neighbors, and not otherwise. A community that would suffer greatly due to the deaths of half the people around them would not necessarily have its average utility increased by that operation.
Without interpersonal utility comparison, the point is moot.
True. Actually, it's worse than that... we don't even have a way to compare an individual's utility over time with any level of precision, though we talk casually as though we did. (If we had such an intertemporal utility comparison, then we could for example declare that the highest-utility state each individual has achieved in their lifetime is 1 unit of utility, and the lowest-utility state is 0 units, and interpolate linearly, recalibrating whenever an individual exceeds their previous maximum, and that would be one way of comparing interpersonal utilities at any given time. Of course, that might not be acceptable because it fails to account for the possibility that some individuals are just worth more than others, or for various other reasons, but it would at least be a place to start.)
Without that, utilitarianism is at best no more than a qualitative way to address ethical questions.
A community that would suffer greatly due to the deaths of half the people around them would not necessarily have its average utility increased by that operation.
You don't have to kill off half of the population to increase average utility.
Consider the following facts:
This sounds a lot like the mere addition paradox, illustrated by the following diagram:
This is seems to lead directly to the repugnant conclusion - that there is a huge population of people who's lives are barely worth living, but that this outcome is better because of the large number of them (in practice this conclusion may have a little less bite than feared, at least for non-total utilitarians).
But that conclusion doesn't follow at all! Consider the following aggregation formula, where au is the average utility of the population and n is the total number of people in the population:
au(1-(1/2)n)
This obeys the two properties above, and yet does not lead to a repugnant conclusion. How so? Well, property 2 is immediate - since only the average utility appears, the reallocating utility in a more egalitarian way does not decrease the aggregation. For property 1, define f(n)=1-(1/2)n. This function f is strictly increasing, so if we add more members of the population, the product goes up - this allows us to diminish the average utility slightly (by decreasing the utility of the people we've added, say), and still end up with a higher aggregation.
How do we know that there is no repugnant conclusion? Well, f(n) is bounded above by 1. So let au and n be the average utility and size of a given population, and au' and n' those of a population better than this one. Hence au(f(n)) < au'(f(n')) < au'. So the average utility can never sink below au(f(n)): the average utility is bounded.
So some weaker versions of the mere addition argument do not imply the repugnant conclusion.