I spent a lot of time in China and ExpressVPN was the norm for the Americans I hung out with. Sometimes though, Express would be down, and I'd spin up a Socks proxy pointing at a Digital Ocean droplet and it worked like a charm. The downside is that only web browsing over Firefox (or the browser configured with the Socks port) will use that proxy, unlike OS or non-browsing internet traffic.
So, yes, VM/router solution will work for TCP connections.
Also there are wrappers which can intercept connect calls to libc from applications on Linux (which is useful if you need to redirect only one application which doesn't support SOCKS proxies): https://linux.die.net/man/8/tsocks