I have two linodes: web server and database server.
They are both connected to each other via private ips. The database server doesn't really need internet access and I can administer it through LISH or from the web server.

Could I use static ips to only connect the private IP and use failover to bring up the database server's public ip on the web server?

If this does work.. Is there a way I could configure a gateway on my private ip's interface settings so I could get NATed internet to do updates?

Yes, exactly how you describe. There is plenty of documentation out there on how to NAT with IPTables, so it should be easy. (I NAT connections through my VPN on my Linode for "untrusted-WiFi-security" sake)