Probably the best VPN out there is Mullvad. It is incredibly fast, reasonably priced, completely private, and supports the new WireGuard VPN protocol.
Update
A lot has changed since this post was originally written, and for the better. For one, the WireGuard Android App now supports user mode, and WireGuard has similar support for macOS, OpenWRT/EdgeOS, OpenBSD/FreeBSD, and of course all the Linuxes. What this means is you can use the app on Android without root and without a custom kernel.
Even better, is that you really don’t need to read the instructions below any more! Mullvad has a new set of instructions that are better than mine, and utilizes their config generator (which didn’t exist when I pulled it all out of their script).
Manual Configuration (Deprecated)
Thing is, WireGuard support is fairly experimental. Mullvad has WireGuard servers, and some basic instructions for using it on Linux and LEDE router. It is also possible to use it on Android, provided you have a kernel with WireGuard support. I figured out this procedure based on the instructions and script that Mullvad provides for configuring WireGuard on Linux (and in hindsight, the router instructions would have been helpful too).
Instructions for Android
Install the official WireGuard Android App.
If it says you don’t have WireGuard support, sorry! Flashing a custom kernel on your phone is beyond the scope of this post. Otherwise, read on.
Update: Kernel support is no longer required! (See above.)
Click the plus button and choose “Create from scratch”.
Update: You can generate this online and import it! (See above.)
Enter a name for the interface (e.g. “Mullvad”).
Click “Generate” to create a public/private key pair. Note the public key.
Run the following command on some computer (not on your phone, unless you have BusyBox or something), substituting in your account number and the public key the app generated earlier:
curl -sSL https://api.mullvad.net/wg/ -d account="1111111111111111" --data-urlencode pubkey="<public key>="
It will return something like this:
123.456.789.012/32,ab12:aaaa:bbbb:cd34::56e/128
Insert what the API returned into “Addresses”. Leave “Listen port” empty.
Put 193.138.219.228 for your DNS servers. Leave MTU empty.
Click “Add Peer”.
Choose a WireGuard server.
Copy its public key into the peer’s public key field.
Leave “Pre-shared key” empty.
Put 0.0.0.0/0,::/0 into “Allowed IPs”.
Put the server you chose with the port 51820, e.g.
se1-wireguard.mullvad.net:51820 into “Endpoint”.
Leave “Persistent keepalive” empty.
Turn on the tunnel! It should connect, and Am I Mullvad? should report that you’re connected with Wireguard. If it’s red, look a bit closer, you’re probably leaking via WebRTC, in which case you should install Firefox mobile, then the uBlock Origin addon, and enable its WebRTC leak protection.
There is also a setting in the app to reconnect on boot, probably want that on.