Have you tried the Silent Circle's phone (Blackphone) [1]?
I'm similar to you in many ways on privacy. If the price can come down for the Blackphone and Celluar data, I'd be all for it. It make take time though.
[1] - https://www.silentcircle.com/products-and-solutions/devices/