I heard some good stories about crossover office. It runs internet explorer on linux. Apparently, it might be possible to run Win32::IE::Mechanize on it. Haven't tried it, though.
Here is a node
How to install Win32::OLE under Linux? which might help. I'm using it to make SOAP service from macros in Excel. While this works, I wouldn't recommend such combination for writing intensive tests of JavaScript web application (it just seems too slow and flaky).
When writing jsFind I opted to create separate html page with tests (which takes a long time to execute) and run that manually in different browsers. This served me well (and enabled me to test JavaScript in different browsers), but than again I didn't have to check interaction with web application and it's interactive approach.
I'm very interesed in solution to this particular problem. Please keep us posted about progress.