This file from Tcl::Tk CPAN distribution has many in common with your questions:

• its a part of perl module to deal with external GUI library
• it creates required widgets on the fly
• it heavily uses AUTOLOAD and brings into existance widget's package where newborn widgets of that class will be blessed

However its not necessary to look into much detail, because actually in case of Tcl::Tk wdiget's package is simple and there is some stub string which is "eval"-ed to create package.

Here are excerpts from code:

$Tcl::Tk::VTEMP = <<'EOWIDG';
package Tcl::Tk::Widget::[[widget-repl]];

use vars qw/@ISA/;
@ISA = qw(Tcl::Tk::Widget);

sub DESTROY {}            # do not let AUTOLOAD catch this method

sub AUTOLOAD {
    print STDERR "<<@_>>\n" if $Tcl::Tk::DEBUG > 2;
    $Tcl::Tk::Widget::AUTOLOAD = $Tcl::Tk::Widget::[[widget-repl]]::AU
+TOLOAD;
    return &Tcl::Tk::Widget::AUTOLOAD;
}
1;
print STDERR "<<starting [[widget-repl]]>>\n" if $Tcl::Tk::DEBUG > 2;
EOWIDG
[download]

and then

# here we create Widget package, used for both standard cases like
# 'Button', 'Label', and so on, and for all other widgets like Baloon
# TODO : document better and provide as public way of doing things?
my %created_w_packages; # (may be look in global stash %:: ?)
sub create_widget_package {
    my $widgetname = shift;
    _DEBUG(2, "AUTOCREATE widget $widgetname (@_)\n") if DEBUG;
    unless (exists $created_w_packages{$widgetname}) {
        _DEBUG(1, "c-PACKAGE $widgetname (@_)\n") if DEBUG;
    $created_w_packages{$widgetname} = {};
    die "not allowed widg name $widgetname" unless $widgetname=~/^\w+$
+/;
    # here we create Widget package
    my $package = $Tcl::Tk::VTEMP;
    $package =~ s/\[\[widget-repl\]\]/$widgetname/g;
    eval "$package";
    die $@ if $@;
    # Add this widget class to ptk_w_names so the AUTOLOADer properly
    # identifies it for creating class methods
    $widgetname = quotemeta($widgetname); # to prevent chars corruptin
+g regexp
    $ptk_w_names .= "|$widgetname";
    }
}
[download]

Actually it could be implemented without any string-eval, (moving CODE to some package, and it will be autocreated), but I decided to go easy way, because it was safe and efficient in this particular case.