I used to work at SmartyStreets, a licensed CASS™ vendor of USPS address data. What you want to do sounds exactly like what they do.
The USPS ZIP+4 file is available from many sellers, but you're right: it only contains about 30-40 million records. We sometimes called it the "ranges" file because it contains address data at a range level only. In other words, it provides street names in cities/states with a range of primary numbers, say, 100-8000, where, in rural areas, only a few of those numbers actually exist.
The full USPS address database comes to licensed CASS™ vendors and the like, which has some added expenses and certification tests.
USPS data contains no geocoding or geolocation data. The USPS' primary concern is mailing: routing and delivering mail. Any correlation between address data such as ZIP codes and actual coordinates or physical proximity is entirely coincidental.
The USPS data is considered a private source. It is expensive to obtain and license, and typically requires conforming to rigorous terms and quality testing (like CASS™ Certification.)
TIGER data is a freely available, public data source. However, it does not correlate to USPS data, except for ZCTAs which were created several years ago. The only way to update that data, as I understand, is to start with the old data and apply all the delta files between now and then.
TIGER geocoding data is not very accurate and is often outdated. (At SmartyStreets, we've been bitten by this before.) Further, converting Census Bureau data into address coordinates is a slow, tedious process.
If you're doing precision skydiving based on TIGER data, you should verify the coordinates yourself. That's how companies like Google, which excellent geocoding capabilities, have amassed much of their data: driving vehicles on all the streets to manually collect map and coordinate data, then aggregate theirs with public sources, to produce very high-quality, competitive, and super-expensive results.
To compensate for poor quality public sources, we've worked with private geocoding services to obtain much better data (rolling out over the next few weeks, in fact).
As for database vs. API -- good luck. The good data is limited to licensed vendors. Google and the like don't hand out their databases at all.
In the end, even though these services all package and distribute their products differently, they nearly all trace back to the same data sources.