Your best bet will probably be the daily First Order Summary of the Day (FSOD) from the National Weather Service.
It can be found in the following location in the Data Library:
/SOURCES/.NOAA/.NCDC/.DAILY/.FSOD/
It is a dataset of stations primarily within the United States. The earliest record begins in 1869, but the last record is from 1999. The dataset does contain daily minimum and maximum relative humidity values, and other measures of atmospheric moisture, including average wet-bulb temperature and average dew point temperature. Not every station in the dataset will have values for all the listed variables, but you may be able to find enough stations for your needs.
-- Michael Bell