What about Opera's FastMail.fm? They are not even based in US, so that might help. I see it's not free anymore though, but it also has no ads, so no tracking for that either.

They could've also used RetroShare for both encrypted chats and mail, and it should've been pretty anonymous as well since it's P2P. This is not something most people would be willing to do, but for someone like Petraeus, it could've been useful.

For most people using something like Jitsi for encrypted chats and video-calls is much more bearable, although you still have to watch-out where you sign-in from and where you create the account, so you'll probably have to follow the whole Tor browser part EFF mentioned in the beginning, if you want anonymity as well.