You're right, it doesn't work with Term::Complete. I thought I had tested it. As you said, it doesn't even use Term::ReadLine.
It works with Term::Shell. Here with the pod example slightly modified:
package MyShell;
$ENV{TERM} = '';
use base qw(Term::Shell);
sub run_command1 { print "command 1!\n"; }
sub smry_command1 { "what does command1 do?" }
sub help_command1 { "Help on 'command1', whatever that may be..." }
sub run_command2 { print "command 2!\n"; }
package main;
my $shell = MyShell->new;
$shell->cmdloop;
Or directly with Term::ReadLine:
use Term::ReadLine;
$ENV{TERM} = '';
my $term = Term::ReadLine->new('Tab Completion');
my $prompt = ">>> ";
&readline::rl_basic_commands( qw(set quit type test run exit) );
while ( defined ( $_ = $term->readline($prompt) ) )
{
exit if /exit/ or /quit/;
print $_, "\n";
}