Your assumption of a US-EU treaty to enforce fines seems like it is one of two intended enforcement methods, the other being the required establishment of representatives to ensure non-EU entities have at least some physical presence in the EU.
The GDPR requires non-EU entities handling EU data to appoint a representative in the EU, and this representative will be able receive the fines or other penalties relating to regulation compliance. In case that doesn't work, according to the text of the GDPR, the enforcement authorities will work with non-EU countries and international organizations to develop exact enforcement methods, rather than having such methods be part of the GDPR itself.
Enforcement Outside EU: Chapter 5 of the GDPR relates to handling of data by non-member countries or organizations. The relevant text relating to enforcement of fines is from Article 50, titled "International cooperation for the protection of personal data":
(1) In relation to third countries and international organisations, the Commission and supervisory authorities shall take appropriate steps to:
a) develop international cooperation mechanisms to facilitate the effective enforcement of legislation for the protection of personal data;
b) provide international mutual assistance in the enforcement of legislation for the protection of personal data, including through notification, complaint referral, investigative assistance and information exchange, subject to appropriate safeguards for the protection of personal data and other fundamental rights and freedoms;
c) engage relevant stakeholders in discussion and activities aimed at furthering international cooperation in the enforcement of legislation for the protection of personal data;
d) promote the exchange and documentation of personal data protection legislation and practice, including on jurisdictional conflicts with third countries.
That's it. Basically, their method of non-EU enforcement seems to be "we'll figure it out". Depending on what 'appropriate steps to develop international cooperation mechanisms' means, it appears like treaties or others agreements will be the mechanism for enforcing the GDPR outside the member states.
Representatives As Means of Enforcement: Article 3 states that the scope of the GDPR covers any data sourced from the EU, regardless of it is actually processed or used there. Article 27 covers the appointment of representatives for non-EU entities, and applies to whatever entities Article 3 applies to. The relevant text from Article 27:
(3) The representative shall be established in one of the Member States where the data subjects, whose personal data are processed in relation to the offering of goods or services to them, or whose behaviour is monitored, are.
(4) The representative shall be mandated by the controller or processor to be addressed in addition to or instead of the controller or the processor by, in particular, supervisory authorities and data subjects, on all issues related to processing, for the purposes of ensuring compliance with this Regulation.
(5) The designation of a representative by the controller or processor shall be without prejudice to legal actions which could be initiated against the controller or the processor themselves.
Basically, non-EU entities which process or control EU data will need to establish a representative/proxy entity in at least one of the member states where they source the data. This representative will, unsurprisingly, represent the non-EU entity in all matters relating to regulation. According to this explanation(and some others I've seen), this means the representative will be subject to any compliance issues, including enforcement of fines.
Presumably, there are mechanisms already in place stopping entities from creating a representative, getting a fine, having the representative declare bankruptcy, and just setting up a new representative.