Programming language supporting infinitary rewriting of regular term graphs?
Yes, Prolog. 

The specification of unification in the Prolog standard omits the occurs check, and as a result variables range over rational trees. Additionally,  many Prolog (such as SWI Prolog and YAP) implementations support tabling, which permits defining and using coinductively defined predicates.