Today I stumbled upon this very useful site that helps you find very cheap virtual private servers (VPS) around the globe. The public IPv4 address is shared and NAT'd across multiple servers. If that's no problem for you, the cheapest servers are 0.15€ a month with 128MB RAM and 1 vCPU.
Also, some public IP addresses are blocked in China and/or Russia.
Have fun!
Reading time: 1 min