Encrypted paper wallets - make your own simple encryption and save the key in your phone/laptop/cloud with a random name and location. When they check your paper wallet and it doesn't work, you tell them it's not a wallet code.

OR

There are tiny cold wallets as well, I'm sure you can get creative with them when traveling.