You've already decided where to put zero when you say this:

If zero is very high, then total utility maximization = it's kill everyone.

That means that zero is the utility of not existing. Granted, it's a lot easier to compare two different possible lives than it is to compare a possible life to that life not coming into existence, but by saying "kill anyone whose utility is less than zero" you're defining zero utility as the utility of a dead person.

Also,

If zero is average utility, then total utility maximization = doesn't matter what you do

does not make sense to me. Utility is relative, yes, but it's relative to states of the universe, not to other people. If average utility is currently zero, and then, let's say, I recover from an illness than has been causing me distress, then my personal utility has increased, and average utility is no longer zero. Other people don't magically lose utility when I happen to gain some. Total utility doesn't renormalize in the way you seem to think it does.