Open sourcing could be a plausible answer. But fighting Google Play clones and what-not is really time-consuming and as an indie dev, my time can be better spent.
What do you suggest?
If some known person (open-source contributor or a startup founder) start using your product, ask for cross-promotion or endorsement of any kind.
Just be open. The more people know about you the more they are inclined to trust you.
I would suggest you open source it under a non-commercial license. Also, take a look at how some successful android open source projects are run. In particular, I like XPrivacy (https://github.com/M66B/XPrivacy). This is an excellent app. Open source with optional purchase, similar to yours. Personally, I paid the $6 they charge because I'd rather not compile the src myself.
You've already had a lot of downloads and are an established app. Clones can't replicate that.. If you are a recognized dev on xda, with your own thread for discussion, feature requests, bug reports etc, no clones will be able to replace that aspect even if they can clone your app.
You should be able to get more downloads/purchases from privacy-aware users. And you can have donations for feature requests if you want.
Just some thoughts.. best of luck with the app!
XPrivacy is a great example. Another one would be "Conversations" XMPP client, that is FLOSS, but is a paid app on Google Play. Even though I wouldn't call it completely mature yet (it's 0.7.x and lacks some polish and minor features), it's a good app that does its job very well and 1-5k users (not bad for non-gratis app, I guess) seem to agree.
A non-commercial license is not, in any sane definition of the term, an “open source” license¹.
However, one thing that I think would greatly help is a privacy notice of some sort detailing exactly what is tracked and how it's used. I don't see one on either the Play store page, nor in the app itself (your site seems to be loading slowly at the moment, or I'd look there too). While it may not completely remove my fears, it would at least serve as a good baseline and would make me feel a little better.
EDIT: Tried your site again, and found your privacy policy. I must say, I do like the way it is written as well as the content. Still, I would encourage maybe a link in the app, at least.
An idea: trust is a huge issue when it comes to development of apps (mobile or otherwise) that transacts important data (and what doesn't these days? Even games could be used to create personal metrics on people's IQ/skills/etc.). Some sort of consortium should be formed to work a coherent strategy on this, anything would pretty much be better than the current day situation: a combination of oath/register/proven-track-record-of-company/technical-guide-lines/technical-validation could prove very valuable resource to consumers and businesses alike!
They can copy your code, but they don't understand it like you do, and therefore can't provide the same level of support or quality in updates. If they copy your code and make it closed source, people won't trust it, and if they copy your code and make it open, you can just steal changes you like back again.
So im sure you can find a place even without making it the first choice for hackers.. but of course you can always take measures to address the concerns of this crowd..
But at first, i think is good to focus on what you are good at; than if you succeed you can grow and address more the security conscious people
Dont try to be everything to everyone else(at least at first), as browser market is crowded you have a very narrow door to pass through, once you find it, use it
(About Trust: it will come slowly with time; It's something you cant get for free anyway.. as in any relationship in life)
Whether/when I have to pay is a little unclear; can you put that front and center? As someone unused to VPN's, I'm a little unsure of what I'm paying for. I'd also suggest changing your payment plans to simply "Monthly, Yearly, and Life". And please, just tell me how much it costs per year in the yearly plan. 1.8*12 isn't hard to plug into a calculator but not something I want to do in my head.
That's not a silver bullet idea though, because it requires trusted voluntary (or not) people and there is always a slight risk of source code leak.
Take a look at the Play store, it's right below the product title ;)