Default webform-form.tpl.php hardcodes rendering order.

I've created a module that renders a "step bar" above the webform - for multipage weforms

I'd suggest just upgrading to Webform 4.x, this functionality is built-into the module now. Though you're right that modifying the template was a requirement for the progress bar. The template now looks like this:

  // Print out the progress bar at the top of the page
  print drupal_render($form['progressbar']);

  // Print out the preview message if on the preview page.
  if (isset($form['preview_message'])) {
    print '<div class="messages warning">';
    print drupal_render($form['preview_message']);
    print '</div>';
  }

  // Print out the main part of the form.
  // Feel free to break this up and move the pieces within the array.
  print drupal_render($form['submitted']);

  // Always print out the entire $form. This renders the remaining pieces of the
  // form that haven't yet been rendered above (buttons, hidden elements, etc).
  print drupal_render_children($form);

This shortcoming in flexibility is an intentional decision to make theming easier. Considering the functionality you're after is now built into the module anyway, are there any problems remaining? I'm going to mark this works as designed, please move back to "active" if you have any further questions.

Hardcoding elements in that way makes it impossible to override in either hook_form_alter() or theme-preprocess functions.

Yep it does, but that's the way it's intended to work. It's a balance between ease of theming and ease of module extension. Some modules include similar approaches, like comment.tpl.php or node.tpl.php. What you're asking for is essentially that there is no theming at all and then entire thing is just a renderable. If that's required on your sites, perhaps you could form_alter the form and remove #theme from the form. I don't anticipate removing the theming from forms to make them more easily modifiable to modules.

That is what weight is for, but in this case Webform is providing a template for demonstration purposes. In 4.x, it's not just ordering that's being used. Unless we switch to #theme_wrappers or a separate theme function for the preview message, we've now got markup that is in the template. Again it's good for demonstration.

For your Webform 3.x module, you can either A) put the progress bar inside of $form['submitted'] (I don't think this causes problems) or B) put a #theme_wrapper on the entire Webform form itself, which will allow you to place things above the entire form if you need.