This should be obvious, but I don't really think anybody thought of it before, given that nobody updated Net::Telnet::Cisco in years, and web search results are really inconclusive :-)
my $ssh = Net::OpenSSH->new($username . ':' . $password . '@' . $hostname, timeout => 60);
if ($ssh->error) {
    print STDERR "$hostname: " . $ssh->error . "\n";
    next;
}
my ($pty, $pid) = $ssh->open2pty({stderr_to_stdout => 1})
    or next;
my $telnet = Net::Telnet::Cisco->new(
    -fhopen => $pty,
    -telnetmode => 0,
    -cmd_remove_mode => 1);
and voila, you can use Net::Telnet::Cisco without actually having to enable telnet on your Cisco router. :-)