Promise was clearly necessary, because without it we had hundreds of other less principled ways to implement async control flow :)
promise.then(function(){}).then(function(){})
async.waterfall([function(){}, function(){}])
Which was: throwing away the entire language's compositional features, including the concept of input arguments and return values, results with... poor compositionality, of course.
It seems you're defining callback hell as 'whatever promises solves' rather than it's common definition of over-nesting.
Node style callbacks are a prime example of how in the quest for "simplicity" and hate for abstractions its easy to build a monster / frankenstein like caolan's async. Node callbacks were a self-contradicting philosophy: it abandoned all thats already in the language in the quest to avoid an abstraction that was not already in the language :)
That said I see how the inconsistency you're talking about with how expressions return values with callbacks and you've certainly put the point very well.
So promises are way more composable than callback based solutions.
async is pretty terrible though, you cannot pass the results from one execution to another, i.e. passing results from one function in async.series to another, which results in developers tending to pollute variable scope by defining above and filling it in inside each callback. This prevents the ability to write clean isolated testable functions.