Running a proxy server
As schroeder says, getting a residential IP would be the real issue. Everything else is simple. You can register a VPS and put a proxy application on it, such as Tinyproxy, a lightweight HTTP proxy that can be configured not to advertise the fact that it is a proxy server. At the worst, it would be advertising in its rDNS that it is a VPS. The ports used can also be easily customized to avoid detection based on common ports. Note that Tinyproxy in particular does not support authorization, so active probing (a technique used by, among others, China) could attempt to connect to it using the CONNECT method on all ports to discover if the server is running an instance of Tinyproxy.
Running a proxy simply involves installing a proxy daemon on a server, configuring the ports you wish to use to connect to the proxy, and opening the ports in the firewall. It's that simple. This can be done on a dedicated server, a VPS, or even a shared shell account. All you need is basic understanding of running a server, and the ability to open ports if they are firewalled off otherwise.
IP and DNS leaks
HTTP proxies do not require you provide the IP address, so the domain will be resolved by the proxy server itself. This is also true for SOCKS5 and SOCKS4a proxies. With an HTTP proxy, requesting an example website is done by sending headers such as the following to the proxy:
CONNECT server.example.com:80 HTTP/1.1
It is up to the proxy server to resolve
server.example.com and relay the response to you.
Getting a residential IP
Using a residential IP generally requires you run a proxy server on a computer connected to a residential line. Unless you have someone who is willing to do that for you, there is no simple, legal solution. If you have online friends who may not mind running a proxy for you, you could take advantage of that. For example, I have a friend in Moscow (Russia) who was willing to run a proxy server on his own system and allow me to connect to the internet through it.
There are several commercial proxy services that can provide residential IPs, however they are rather sketchy at best of times, and certainly are not what I would call "trustworthy". Many of these services are likely to run proxy servers on a botnet and sell access to the proxies for a profit. While this may give you a residential IP (and "reputable" services will guarantee that IPs will not be shared, or will be minimally shared), it is likely that it is running on a compromised machine. An example is VIP72, which has been known to (perhaps unwittingly) utilize botnets.
It is also possible to exploit consumer routers and run lightweight proxies on them. Many routers have vulnerabilities in exposed web interfaces, or even just use default credentials. As the majority of routers are rarely if ever updated and behave as magical black boxes to their owners, detection is exceptionally rare. Scanning the IPv4 range for particular router vulnerabilities can prove very fruitful. Relevant vulnerabilities are often posted to mailing lists such as Full disclosure. Note that this information is for educational purposes only, as hacking routers is illegal in many jurisdictions.
Encryption is not needed. Encryption through OpenVPN introduces its own issues of detection - or this is what I have read.
That isn't true. The OpenVPN protocol does not hide the fact that it is a VPN tunnel from your ISP, but the website you connect to will not know anything about that. The encryption used by OpenVPN (or other encrypted tunnels such as IPSec) terminates at the VPN server. There are other ways to detect that a VPN is in use though, so a (secure) proxy can actually be more stealthy.