I've considered printing the private key portion in invisible ink, which requires a special reader, and doesn't allow the printing party to view the QR code, but even this involves an element of trust in the minting process, and would also require that the private key and QR code is not visible as the paper wallets are generated.
Who's "the printing party"? If you're outsourcing the printing, you're increasing the risk of someone gaining access. Invisible ink doesn't make that impossible.
Perhaps the only way for someone without Internet access to securely purchase bitcoin is at a BTM that prints a paper wallet as he deposits the cash. But one still has to trust the BTM and those who operate it - or have some type of escrow or reputation trademark.
I wouldn't trust the private key from a Bitcoin ATM for long-term storage. Sweeping it to your own wallet is the best thing to do. Why would anyone want to "use" Bitcoin without internet?
By way of comparison, many industries - including banking - are overly trusted. It's a double standard. But I will continue my quest for trustless money.
I don't trust banks at all, but I'm still forced to use them.
No need to look further: trustless money (Bitcoin) exists already. But if you're looking for trustless offline money, maybe gold works?