Theme the progress bar when in batch API with AJAX
Ultimately decided to use the hook hook_js_alter() in order to replace misc/progress.js with my own version. You can declare your own markup in this file, and also react on progress update (every 1500 ms out of the box).

In case anyone was wondering, this is the outcome of this http://drupal.org/project/nyan