I admire your methodical structuring of the issue but, for completeness, there are two more possibilities:
3) Improve the battery, i.e. better battery chemistry to give more power per cubic centimetre of volume.
4) Augment the battery capacity by mobile charging, something like solar, thermal (from the heat of the user's hand and pocket) or kinetic (movement, as used by automatically winding watches).
You most definitely listed the the two most immediately significant factors. Looking at the full list in turn:
4) Right now the power these technologies could put back into the battery compared to the power being drawn out of it is insignificant but, like I said above, I list it here for completeness. One day I believe that these technologies will come into play.
3) I'm not an expert on battery chemistry but from what I've read the progress in innovative new chemistries has been stalled for a while with no real prospect of a significant increase in mAh per cc on the horizon.
2) I suspect that, even though the iPhone 4 internals are sometimes described as almost all battery, there is still scope for some increase in battery size due to even more integration of the electronics but it's not going to get much more than 10% increase.
1) This is where there is still scope for significant improvements. Apple have invested vast amounts of money in capabilities to design their own electronics, primarily CPU and GPU - they've bought two entire companies specializing in this. I suspect that they will be able to get something like a 75% increase in performance per watt on the successor to the A4, some of which they will use to increase battery life, but some will also be used to boost performance. It will be interesting to see how Apple allocates the increased performance per watt between increased battery life and increased performance.
The other big power drains are the various radios and the screen and, as the CPU/GPU gets more efficient, these become by far the most significant factor. I'm really hoping that they might be able to do some sort of tricks with the technology and/or production of the screen because that's what's going to make a big difference.