Out of IPs on a dedicated server with lots of resources and VPS capabilities... Options?

So, I'm out of IPs and the colo company for my dedicated server wants to charge an insanely high amount for a block of 5 more IP addresses.

I'm wondering if I'm screwed or if there are other alternatives to getting an IP on the box? I can setup VPS with NAT using the dedicated server's IP to have internet, but I am wondering if there is an option to get more public IPs either through some kind of tunnel or VPN etc?

Does anyone have any insights into a cheap and reliable way to get this done without having to give in to extortionist IP prices from the colo provider?
Thanks!