I'm aware of Modern Perl and recommend it for every novice, but as you mention, it is not a tutorial and thus doesn't have much to do with what the average newbie is looking for. It's also not readable on the web.
Cheers. For what it's worth: My main concern in this is that any kind of widely-used perl tutorial needs to inherently updatable by a wide group of people. Modern Perl would make the cut because it's hosted in Git and a website could easily be generated from there in regular intervals.
