How long does one need to be in the EU to have/exercise that right?

E.g., could an American issue a deletion order during a layover in a European airport?

I believe you just need to be a European resident, although how you define that is the crux. Realistically if you have a way to prove an address you reside at in Europe, that should be sufficient.

I do not live in the EU.