I am aware that a botnet would work because I could just use my users as proxy, but I really dont want to do that.
I rarely have any issue with youtube through tor.
They're going after youtube-dl.
This is a pretty exhaustive place for comparing VPS providers: https://lowendbox.com/
Also, I just found this dedicated server provider: https://www.kimsufi.com/en/servers.xml
The prices are insanely low considering that these are dedicated servers, not VPS's. For example, you can get 4GB of RAM, 2TB disk space and a two-core Intel CPU for €6 a month.
how the fuck have you managed to get IP banned by google?