It's probably not turned on in your xinetd.
You don't say which RHEL AS you have (1,2,3, 4 or 5).
From my RHEL AS 3 box in /etc/xinetd.d there is a file called "rlogin". This file contains:
# default: on
# description: rlogind is the server for the rlogin(1) program. The server \
# provides a remote login facility with authentication based on \
# privileged port numbers from trusted hosts.
disable = no
socket_type = stream
wait = no
user = root
log_on_success += USERID
log_on_failure += USERID
server = /usr/sbin/in.rlogind
You have to set the "disable = no" for it to actually listen for the connection. rsh requests are answered by rlogin.
Not sure why you're seeing "no route" unless you're also blocking the port (513) in firewall. You should get "permission denied" instead. You might try temporarily disabling iptables and SELinux to be sure neither of those is blocking it. Also if there is a firewall device (bridge/router) between the machines you'd need to verify it is n't blocking the port either.