If you have access to ping you might be okay. Depending on the version you have installed you can replicate traceroute manually by setting the TTL (time to live) of the ICMP packets. This is exactly what traceroute does.

The command:
ping -t 1 www.google.com 1

Does a ping with the TTL set to 1 (the -t option). The 1 following the host is the number of times to attempt to connect. So this sends out one packet with the TTL set to 1. The first host that this hits decrements the TTL and checks that it is > 0. If the TTL is not > 0 then it sends an ICMP packet back to the sender telling it that the it is undeliverable since there were too many hops. Next you send another packet with a TTL of 2 and see which host refused it. Keep doing this until you hit the target (or send some maximum number of packets to prevent looping forever) and you will have some path through the network.

My output on Solaris 2.7 looks like:

ICMP Time exceeded in transit from pos5-0-2488m.cr1.snv3.GBLX.net (64.
+211.147.14)
 for icmp from bbsun (216.91.233.128) to www-su.GOOGLE.com (64.208.32.
+100)
no answer from google.lb.google.com
[download]

And on Linux 2.2:

PING google.lb.google.com (64.208.32.100) from 208.176.85.42 : 56(84) 
+bytes of data.
From 208.176.85.41: Time to live exceeded

--- google.lb.google.com ping statistics ---
1 packets transmitted, 0 packets received, +1 errors, 100% packet loss
[download]

So you will have to parse the response for your machine (also the arguments are different).

Unfortunately the Net::Ping module does not support setting the TTL. But if it did you would need to be root to send ICMP packets. And if you have root access you may as well compile traceroute for that machine :-)

-ben