Googling your issue I found 2 links of interest:
- https://github.com/EthanRBrown/rrad that provides approximately 3200 real anonymised addresses.
- https://openaddresses.io that also has a link to their open source github with the complete data set.
I don't recommend scraping the fake address generators as they do not guarantee existence. I would not go sampling in google maps either as you will surely get blacklisted.
Extracting data from downloaded zip file in 2 is easy: they are zip files containing csv files with full address, zip, lat, lon, etc...
The two above data sets "guarantee" the existence of the address. I don't know how hard your other conditions are, namely having at least one valid address for each of the 41k zip codes. If this is a hard constraint, I doubt you will get such data set open source.
EDIT:
If you have a list of all postcodes in the US, a fully automatable solution is by using a service called nominatim of openstreetmap(subject to their TOCs!)
1) get the lat, lon (centre point or default address) of each post code:
https://nominatim.openstreetmap.org/search/?format=xml&addressdetails=1&limit=1&country_codes=us&postalcode=35051
2) get the related address of this lat, lon:
https://nominatim.openstreetmap.org/reverse?format=xml&lat=33.178764&lon=-86.619038&zoom=18&addressdetails=1
trying this example for Columbiana in Alabama (postcode 35051) yields 397 West College Street.
Nominatim documentation is at: https://wiki.openstreetmap.org/wiki/Nominatim