Hi,
Try webhostingtalk-forum's vps-/dedicated- hosting offers-section,
lowendtalk/lowendbox and similar.. search bitcoin for example to find hosts
accepting that..
Much recommend googling such as somehost.com+review first, as well as
reading their terms & conditions - some hosts are outright bad or otherwise
prey on people who don't.
Some have strict fraud screening and verificaitons, most don't.. usually
find info in their policies.

There are many VPS hosts offering root on a XEN VM for a few dollars to
ten-twenty per year for example. For best offers may want to keep an eye on
the offers section over some time, as very good offers from good hosts
often get sold out quickly.

This allows setting up VPN-software (such as OpenVPN) for much cheaper than
most commercial VPN-providers, and, depending on purpose, may be beneficial
for sake of not appearing as a VPN-provider at all.

For the newbs, or anyway want an easier way to deploy OpenVPN relays
quickly one could use an auto-install "road warrior" script such as those
found at github.com/Angristan & /Nyr (in their repos..somewhere,ifnot seen
on the first page)

Besides possibly allowing some more control in various ways for the VPN
configuration or software itself, can use this along with full-disk and/or
containerized encryption, custom personalized DNS services and more. Also,
using a few of these few-dollar hosts and having paid with BTC and some
random details and with a more-or-less safe IP (beware; many known
proxy-/vpn- IPs when used during sign-up easily trigger warnings and may
cause additional verification to be requested) could enable quickly and
easily setup of numerous VPNs in a chain (similar to what VPN-providers
would advertise as "multi-hop" VPNs), with as many hops as you'd please, or
used tactically for specific purposes.. (for example having
commercial-provider VPN service as the end-node/exit-relay, appearing to
others online as using such a service (for whatever reason) - as an
example.

Another beware; careful with hosts specifically emphasize accepting
Bitcoin, offer "anonymity"/"privacy"-focused services/servers.... if not
for sake of things like increasing potential for being targeted due to
possibly presumed more valuable data, the fact you'd find and want to use
such services surely means others would too-- others who you'd not want to
share hosting provider with such as people quickly buying a VPN to use for
hosting illegal content, send unsolicited bulk-mail (spam) and such,
knowing their accounts get terminated quickly but indifferent likely having
used fraudulent means of payment, fake ID etc .. and often leading to
trouble for the host, and at worst case making the host eventually close
down or otherwise get trouble that most others wouldn't wanna be affected
by..

Hmm.. I should end here soon.. Sorry; I talk alot .. Just wanted to
suggest renting a server on your own as such, as some may not be aware it
may be as easily and fast (many hosts, VPS-providers especcialy, offer
instant-activation of servers upon payment (BTC- and CC-payments atleast)
and how it may allow setup of a large number of servers with only minutes
spent on each using auto-install scripts as mentioned above..
Also, likely cheaper than many VPN-providers anyway;) I've got a bunch of
VPS servers for just a few dollars per YEAR!

Again just to reiterate one often important point.. their their ToS/privacy
policy, as some hosts are jerks or simply very strict. Follow
offers-sections for especcialy good deals, and preferrably search reviews
online and on forums before going with a host. May also want to search for
like host+(coupon|sale|promotion|special|bargain|discount) , see their
twitter/blow or such too for a lower price possibly..

hm.. - yeah, I should prolly end here for now..


Good luck anyway!:)