Use ssh if the device your connecting to supports it and it's configured.
How does your telnet not work?
If the shell says command not found, apt-get it.
If you get connection refused, the device your trying to connect to is not listening on telnet's port 23 (assuming your not specifying a port on the command line).
If the telnet hangs for a while for the connection to time-out, make sure the remote ends is on, check network connections at both ends (the pi and the remote device), check IP is correctly configured at both ends, and finally remove any firewalls (hardware or software, including ipfilters and windows firewall) between both ends.
Telnet is a very useful tool and is more often used these days for problem diagnosis (and spoofing SMTP) rather than remote login sessions.