Contrary to what most people think, traceroute actually (by default at least) sends UDP packets to high-numbered ports, not ICMP. The ICMP responses along the way is how it figures out the route, but it doesn't have to send these.

However, the UDP packets are somewhat mangled in order to get the proper TTL values (as you indicate), so root/administrative privileges are still required.