What do you have available?

If Net::Telnet is there can you telnet back onto you own server? That way you may be able to emulate a sort of Expect by capturing return values and sending responces. ie telnet to localhost, then SSH from that out to remote box.