There is an exception to this.
In your AUTOLOAD you can create an anonymous sub and install it in the symbol table by assigning to the typeglob for the value of $AUTOLOAD.
Try this as a very simple example (read don't use in production as is)

#! /usr/bin/perl -w
use strict;

print "NOT LOADED\n" unless FOO->can('bar');
FOO->bar();
print "NOW LOADED\n" if FOO->can('bar');

package FOO;

use vars '$AUTOLOAD';

sub AUTOLOAD {
    no strict "refs";
    my $class = shift;
    print "LOADING $AUTOLOAD\n";
    *{$AUTOLOAD} = sub {print "USING CACHED VERSION";};
    return 
}
[download]