You're being blinded by your goal. You need to be thinking about how to bypass your problems, not choosing an end goal, and focusing only on working towards it -- if you do, you'll miss the other paths that might come up along the way.

Try this as a possible work around:

1. Set up a CGI at a new URI.
2. The new CGI proxies the connection to the old CGI, but reformats the output, to something that is easily parseable.

So, you've solved the issue with the users not needing to install HTML::Parser, and you've not re-written the original CGI.