I think I would still use Net::Telnet, and build an interactive shell into your script that passes on the user entered data on via Net::Telnet to the remote shell. See PPM on ActivePerl and CPAN (the module) for examples of what I'm thinking of. Also check out the module Term::ReadLine, which modern versions of CPAN.pm use, to write the command line interface for this side.

Oh, look, no code. But you didn't provide any code either, so I won't feel bad about it. :-)