Theory says that there shouldn't be any ICMP error messages for ICMP messages. When sending ICMP echo requests in traceroute, doesn't this break this rule?
The theory you mention was never a standard. In fact, RFC 1393, Traceroute Using an IP Option created a Traceroute option. This RFC has now been moved to Historic status by RFC 6814, Formally Deprecating Some IPv4 Options, Section 2.3. Traceroute:
The Traceroute option is defined in [RFC1393]. The Traceroute option is defined as Experimental; it was never widely deployed on the public Internet.
A Traceroute tool is still part of most OSes, but it is often misused. It is really only useful on a network that you control, and you know what the results should be. Using it on public Internet is really a fool's game because many ISPs will purposely reroute the packets and/or set them to lower priority, and your result will not reflect what happens to your other protocols.