Apart from Apache::ASP, I've personally worked with standalone cgi's and HTML::EmbPerl. Also, I've had some second-hand experience with HTML::Mason. The basic run-down is:

• HTML::EmbPerl -- Don't bother. It's too much of a toy-like construct. Everything it does, Apache::ASP does in a more transparent, useful, and perl-ish manner. Also, Apache::ASP is written completely in perl, whereas HTML::EmbPerl is written largely in C/XS, which just lends itself to being a pain to deal with problems. Also, in its earlier incarnations, lexical scoping (use strict pragma) was impossible to use, and when it was fixed later, it was so done in a very cobbled-on, hackish way. It was a nightmare. In the end, we (I) wrote a script to completely rewrite a large application from HTML::EmbPerl to Apache::ASP, because it just became too much of a mess to deal with. That was nearly three years ago, and we have not yet regretted the decision.
• Standalone CGI -- I don't think I have to make an argument here for why, particularly in a large application, some form of templating as well as some form of application server framework (for things like caching of the compiled code, possible integration of things like session management, and so on) is a Good Thing.
• HTML::Mason -- (speaking second-hand, here... please forgive / correct if I say something wrong) Mason is a pretty nice framework in its own right, but it is geared more toward content-heavy web sites, and less toward big applications.

Also, it goes without saying that you want to be using Apache::DBI to your data store (assuming that you will be using some kind of relational database).

Anyway, I would still investigate HTML::EmbPerl and HTML::Mason, as I'm just giving you my opinion (for one) and some friends' / colleagues' opinions (for the other).