That list represents most of the browsers people care about, with the exception of old IE. And "better with a modern browser, manages to function on old IE" seems like the right standard to shoot for most of the time, depending on your site's audience.
The pattern Async Analytics uses works in all browsers and it's simple enough that you don't need a library for it:
var script = document.createElement('script');
script.async = true; // enables out of order execution
script.src = '…'
var s = document.getElementsByTagName('script')[0];
s.parentNode.insertBefore(script, s);
While parallel script loading is cool, it's been done by a number of other script loaders. What's neat about HeadJS is all the other stuff! a smaller version of modernizer, pseudo media queries, etc. I quite like it.
I had some serious issues with head.js with http://blitz.io in that the load order was not deterministic causing all sorts of weirdness. For example jQuery will end up loading after the code that requires jQuery resulting in undefined stuff and form posts not binding properly. While I truly liked the idea, it wasn't for us.
The HeadJS website says scripts will "run in order", you must have had a buggy version.
I have successfully used LABjs (labjs.com), it has more fine-grained control over parallel/serial loading and execution. For a single project. One of the goals was to parallelize script loading, but modern browsers already do that, they will load up to 4 js files in parallel and execute them in order. In the end the performance gain does not justify the added complexity.
Also worth noting is Steve Souders' control.js (http://stevesouders.com/controljs/) which adds some tools for delayed script execution and solves a few document.write use cases that have been issues with deferred loading/execution.
http://news.ycombinator.com/item?id=2780233
And this does the same thing without using proprietary code:
(and head.js won't do anything special in browsers where the above line isn't supported anyway)