You might need to increase your budget a little for reliability, and would also suggest looking into getting a VPS if at all possible
First of all you need to raise your budget and secondly you might have to go for a offshore hosting provider because many UK and US hosting providers do not support proxy.
While this is true in most cases for shared hosting, a lot of providers will allow proxies on their VPS/dedicated plans and not their shared/reseller platforms. Best approach here is to find the hosts you're interested in and ask their support if it is allowed.
You don't need a PayPal account to pay via credit card. So any PayPal provider should be able to help you out