First, if you didn't go in person to inquire about a birth certificate to the county you believe he was born, if it is close enough - GO! Oftentimes these records are indexed by hand, and by someone with bad handwriting. It was a famous story in my family that grandma had to get her driver's license with a death cert. made out by a overanxious doctor. Her name was thoroughly misspelled in the register (and out of order), but I found it.
Then I would suggest would be checking the marriage records for your grandparents. The county clerk (or other official depending on your state) would likely have an application for marriage in which he would have provided info on his parents, birth date & place, occupation, whether married before, etc. If that information isn't in the application then check the church that the ceremony was at, if any. (If Catholic they might have the church he was baptized at.) If that is a no go, you might check for a wedding announcement in your gm's hometown. Also if your dad (or one of his sibs) has a baby book, check it.
If that doesn't get you anywhere look for siblings if he has any, these tend to be mentioned in marriage announcements, obituaries, and probate proceedings. I only know my mat. gm's g-g-gf, because it was listed on the death cert for his sister.
Also if he was in WW2, check and see if the town he enlisted from, or where you believe he lived has a book on WW2 local soldiers (or browse through the microfilm for that time yourself). Some have photos, clippings of letters sent home, etc.
Also check and see if there is a historical society library in the county your gf lived most of his life in. Often their collections are different than the libraries.
Also if this is the same gf as in your other post, did you only check WPA index records at the library or did you go to the Health dept? The WPA index for Indiana, while it did go to 1920, had a lot of missing info. So go to the health dept.