Provided I used a secure encryption algorithm and a long and random encryption key, then I could quite safely store it online, especially if it is only going to be for a short period of time (say, the 12-24 hours needed to take a flight, get through the border, retrieve the data, and sweep the bitcoin to a new wallet).
The caveat to this is the long and random encryption key. To be as secure as a 24 word phrase, you would need 39 random characters drawn from the full ASCII set.
This is the best case scenario, where you have the right password length & combination and where you store the proper thing the right way. We have some encrypted ".dat" files on the forum that you have most likely seen too around, which haven't been decrypted in a decade.
But the average Joe would think that the same password they've used on 100 other accounts, although long and complicated, is secure to use for a paper wallet encryption and post it on a forum too when you have password leaks happening every day so the long, very complex password might actually be a Google search away. I can't even recall how many times I thoroughly thought of a security process to make sure everything is as should be, but months later I found out a very little thing I forgot could've led to the compromise of the provided security all that time.
Hence, I'd rather take the encrypted key with me on a piece of paper and take just as much care of it as I would of my physical fiat wallet; I think it's the best suggestion one can give to the average person. Honestly, unless you are a very important/suspicious person as you said Snowden would be, I think the chances are almost non-existent that someone would check out what you wrote on a piece of paper. At least for now, because if Bitcoin ever becomes the norm, expect paper thieves to exist, lol.
I personally do not trust online backups of any sort, especially financial assets. Online means possibility of leaving fingerprints in a
server you don't own and, if anyone is interested in running with their Bitcoins
from someone/something, I guess it'd be even worse to leave traces.
EDIT: The "average Joe" part now makes even more sense after Tash's reply:
If someone is stupit enough not to remember a 8 character password, it does not deserve a coin.