efficacious,
You do have one further option. Although I wouldn't recommend it.. however it doesn't require javascript OR flash.
You can have an iframe in the area of the page that needs a progress bar, and use PHP to display a text or graphic progress bar. You can use a javascript AND meta refresh (to take care of js/non-js users).
Using text would be fast enough to appear as if it isn't refreshing, although it is.
You would follow the same principal as the flash idea, whereas you use session data to update the completion percentage.
Once the iframe refreshes, it can be the "second" php file (as I mentioned earlier).
You can insert a <noframes> tag to handle those few customers who do not handle frames, to say "Please Wait for the process to complete. This may take several minutes. Please do not refresh the page or navigate away"
You can then insert a meta redirect at the process completion to move to a new page informing the noframes user that the process is complete.
It may be the only way (that I can think of) to have a progress bar without relying on JS/Flash.
Please note: If you decide to use a graphic, make sure that it is a gif and no more than 2px wide, ensure it is only ONE color to reduce the filesize so that it will load quick enough.
Also, The <noframes> tag is not allowed in XHTML 1.0 Strict DTD. So check your DTD on the page that is doing this work.
If you dont mind the work, setup the JS way, use the iframe in the <noscript>, and the <noframes> after that.
This way you can setup a stepping stone of the "best" and "just ok" progress bar(s).
Link to detecting flash / replacing with an image in JS
Using JS to detect Flash
And Finally:
Dynamic Progress Bars in PHP
I hope all of this works for you..