States can't leave the USA countries can leave the EU, which is a massive difference. NAFTA and EU are not countries they are an agreement between countries.
States can leave the US with the consent of Congress. Congress has never given its consent, and it is hard to predict how it would behave if such a request was seriously made today. Congress did reject the demand of the Confederate states to secede, but there was a strong moral argument against allowing their secession–their primary reason for secession were to continue to evil practice of slavery. If a state wanted to secede today, I doubt there would be such a strong argument against allowing them to do so.
EU member states have only been able to unilaterally leave the EU since the Treaty of Lisbon came into force in December 2009. Prior to that, there was no legal provision for a member state to leave without a treaty amendment. So the situations between the EU and the US are not as dissimilar as you suggest.
Well, it is definitely possible by constitutional amendment, which normally means a two-thirds majority of Congress and 75% of the state legislatures. (Or the convention process...)
But, I don't think we can definitely say that a constitutional amendment is necessary. Suppose that a state requested to secede, and the request for secession was approved by both popular vote and by the state legislature; and that Congress then passed ordinary legislation approving the secession. Would the Supreme Court rule that legislation unconstitutional? I don't think anyone can really predict how the Supreme Court would act, but I don't think it is certain that they would rule it unconstitutional. But if it is possible that they might not rule it unconstitutional, it is possible that secession with Congressional consent is constitutional. Certainly it would be easy for the Supreme Court to distinguish this scenario from the Civil War scenario of attempted secession against the will of Congress, if a majority on the Supreme Court felt so inclined. If the majority of Congress, and the President, was in favour of permitting the attempt at secession, the Supreme Court might not be inclined to overrule them.
What counts is not what the document literally says, what counts is how it is interpreted in practice. And when dealing with hypotheticals, no one can really know how it will be interpreted in practice unless and until that hypothetical becomes an actuality.
> States can leave the US with the consent of Congress.
No, they can't. The Constitution only provides for rules on forming new states and forming states from parts of other states. There is no text on what happen should a state decide it wants to live. In the Civil War, some states argued that the Constitution was a voluntary compact of sovereign states, such that a state could unilaterally leave if it so desired (no need to get consent of Congress). SCOTUS later held that these declarations of secession never held validity.
EU member states have only been able to unilaterally leave the EU since the Treaty of Lisbon came into force in December 2009. Prior to that, there was no legal provision for a member state to leave without a treaty amendment. So the situations between the EU and the US are not as dissimilar as you suggest.