This is somewhat misleading; usually when one discusses a browser's JS capabilities, it's referring to the actual abilities of the browser, such as does it support native XMLHTTP? Does it support ActiveX? etc.
Regardless, there is no way to reliably deduce the processing power or speed of a browser. One might think that you could run some simple stress-tests, compute the result and compare to a list of past performances to see where the current user's browser ranks, and possibly use this information to arrive at an estimated time. The problem here, is that these calculations can not only be influenced by activities in the browser (or merely on the OS); for instance, you run your profiling script, and the user's AV scanner starts up because its 5pm; what normally might take 2s, takes 20s.
On thing to ask yourself, is: Does this processing have to take place right NOW? As n8wrl and Beska alluded to, you might need to code your own method whereby you break-up the work to be done into chunks and then you operate on them one at a time and using something like setTimeout(). This will give the engine time to 'breathe' -- and thus hopefully avoid the 'unresponsive script' warnings. Each of these chunks could also be used to update a progress bar (or similar) that gives the user some indication that work is being done.
Or you could take the approach like GMail - they flash a very small, red "Loading..." text area in the corner of the window. Sometimes its there for a few seconds, sometimes it's not there long enough to read it. Other times it blinks on-and-off several times. But you know when its doing something.
Lastly, also on the point of incrementally 'building' the page, you could inspect the source of Chrome's new tab page. Note: you can't view this using "view source"; instead, choose the "javascript console" option (while on the new tab page) and then look at the HTML source there. There should be a comment that explains their general strategy, like such:
<!-- This page is optimized for perceived performance. Our enemies are the time
taken for the backend to generate our data, and the time taken to parse
and render the starting HTML/CSS content of the page. This page is
designed to let Chrome do both of those things in parallel.
1. Defines temporary content callback functions
2. Fires off requests for content (these can come back 20-150ms later)
3. Defines basic functions (handlers)
4. Renders a fast-parse hard-coded version of itself (this can take 20-50ms)
5. Defines the full content-rendering functions
If the requests for content come back before the content-rendering functions
are defined, the data is held until those functions are defined. -->
Not sure if that helps, but I think it does give insight into how some of the big players handle challenges such as this.