So it's a tall order but the NSA doesn't have infinite resources nor infinite clout particularly not outside of US jurisdiction. Infiltrators are always possible but also high-risk endeavors with huge political consequences. You can at least try to make the risk/reward ratio seem unappealing. After all, the current standards were made when strong encryption was neither computationally feasible nor publicly available. The main downside is that people don't want to carry around their encryption keys so I think you'd have to define at least three security levels:
1) The server does the decryption for you, trust the server
2) You download the encrypted message and your encrypted private key and must input a secure password (read: long) to decrypt, either once (stored on device) or every time.
3) You bring the encryption key yourself.
Honestly, already just the first one would be pretty damn good.... I want to email firstname.lastname@example.org, the server asks example.com for his public key and verifies through DNSSEC that I'm actually talking to example.com then provides his public key back to my local client/javascipt webclient. I can verify the fingerprint, message is encrypted client side and sent to server. The server transports it over SSL to the destination server, not even metadata snooping unless you 0wn any of the servers or SSL itself. That's my side secure, the rest is up to the recipient and how paranoid he is. For example a corporation might feel their corporate email server and internal network is secure enough, there's no need to have personal passwords for every employee. The mail server at yourcorporation.com receives it, decrypts it and you collect it the old way.
The problem is getting the network effect kicked in, email has value because everyone else has email. If nobody has a clients or servers that talk the new protocol it won't go anywhere.