I give this link to so many people that I already know the node id by heart :-)

Update:you said without, while I read "with"...

Also these two recent nodes:
existing PERL modules?
Installed Module

perl -MFile::Find -le 'for (@INC) {
    find(sub { print $File::Find::name if /pm$/ }, $_)
}'
[download]

Update: here's one that cleans up the output to resemble the module names, rather than the .pm filenames:

perl -MFile::Find -le '
for $inc (@INC) {
  find(sub {
             return unless /pm$/;

             ($module = $File::Find::name) =~ s!^$inc/!!;
             $module =~ s!/!::!g;
             $module =~ s/.pm$//;

             print $module
           },
       $inc)
}'
[download]

Also worth a look: pmdesc2 - lists modules with description

There's also a reply I posted on how to make a locate database out of it.

perl -e 'foreach $a (@INC){next if ($a eq ".");if(-d $a){@m = `nice fi
+nd $a -name *.pm`;} map {s/^$a\/?(.*)\.pm$/$1/;s/\//::/g; push (@n,$_
+) if ($_!~/\.|-/);} @m; print @n;}'
[download]

File::Find has been part of the standard perl distribution since 5.00307, which was released in Oct 1996. I think it's safe to assume most perl installations have it available, and you can avoid rolling your own path traversal code. :-)