Why would you not recommend Ubuntu? It's been several years since last time I use desktop version but it was pretty good then.
edit: just wanted to mention that when I first installed ubuntu I forgot to disable the feature, performed some very innocuous searches, and was shown loads of porn results from Amazon. That alone makes the feature completely worthless and frankly dangerous (depending on the environment that you're using ubuntu in).
1.) No Internet access (the default)
2.) Route through Tor
3.) Route via VPN to a server at home and out through my broadband connection (I trust my broadband ISP slightly more than my mobile network provider). This protects me on untrusted WiFi networks too.
[edit] I wish I didn't have to do all this, but the smartphone OS market doesn't give me non-leaky OS options in the same way that the Desktop market does.
Luckily Cyanogenmod supports my phone. I will attempt the installation soon. Any piece of advice, or something you would like have known when at my situation?
edit: nm, based on the other downvotes in this thread I'm guessing zealots at this point.