NEXT doesn't like this because it uses caller to find the calling package, and caller sees the package the function was compiled in, not the one that was called.

You have the right idea with the eval approach, but I was suggesting something more like this:

sub import {
    my $package = shift;
    my $methodname = shift;
    my $dest = caller;
    my $compiled_in = __PACKAGE__;

    # The initial comment improves error messages.
    eval qq{# line 1 "Loaded by $compiled_in\::import"
        package $package;
        sub $methodname {
            return shift->SUPER::blah();
        }
    };
    die $@ if $@;
}
[download]

Also note that your imported symbol can make use of closure variables without interpolating them. If you put \$foo in your code, that will be compiled as $foo, and that will pick up any lexical $foo that is in scope when the eval happens.