My dad was adopted in Detroit in 1930, so I feel your pain.
Since my father is deceased (and most definitely his birth parents), even though the State of Michigan says I as heir am entitled to his original birth certificate, Wayne County refuses to comply. I do, however, have all his original adoption papers. Unfortunately, back then, adoption papers contained no more than the mother's name and year of birth. And she had a very common name - if it was, in fact, her real name. She may not have even come from Detroit or Michigan, so I do not trust my Census searches of her name.
I have been tested at all three services, my brother has been y-DNA and atmDNA tested at FTDNA and my mom has been tested at FTDNA and Ancestry, so I have a very wide pool to muddy the waters. But with the several tools I have in my arsenal, I know that it's just a matter of time and luck before I find the smoking gun that leads me to my father's birthparents. I always keep in mind that more and more folks get tested everyday, and that ultimately, we are all related - I'll find my grandparents.
Your dad needs to get yDNA tested at FTDNA so he can at least get a potential surname. Now this is no guarantee that you will discover his father due to non-paternal events and adoptions that could have had happened generations ago, but you may hit gold if you find that he is matching a pool of men descended from John Smith, c. 1800 who are involved in DNA project. FTDNA will tell you if there is tree available, and if not, you can always reach out to the matches and ask them if they have trees you can view. Because FTDNA only shows direct ancestors, you'll need to build out trees of any suspected ancestors and add brothers, sisters, their husbands, cousins, aunts and uncles, etc.. Again, you may not find the ancestor right away - it's more like finding a needle in a haystack actually! And a 2nd cousin match could actually be a 4th cousin - if you share more than one line, which is very, very possible. (I have a 3C1xR very easily verified, solid match that is showing as a 5th-8th Cousin match here at Ancestry - it all depends on how much DNA your parents passed down to you. Apparently one of us got less than the anticipated 3rd cousin threshold). And I have 8th cousin matches from a matriarch with children from 3 husbands that emigrated here in 1717. There were a couple cousin marriages in the mix, so apparently some of us have retained enough DNA to point us back to my 7th great grandmother. DNA strong like bull!
23andMe has returned the closest match yet to my paternal side - a second cousin as well. He was very generous in providing me his parents, grandparent and great-granparent's names, and I've just built a tree of 2000 individuals from that information looking for candidates for my grandparents. Of 2000 folks, there are about three couples that I can place in Detroit in 1930 - but their surnames do not match the yDNA results for my brother, or the name on my Dad's adoption papers - However, some of my match's ancestors did marry into families that share surname my brother's yDNA test identifies with. All these are clues that may lead me to the jackpot, or they might be a deadends.
On the other hand, since I am fairly certain that I found his grandmother as a match here at Ancestry, and that she is only a 5th - 8th cousin match, I have to assume that the grandmother's line is not where I'm going to find my dad's parents or grandparents, so I can now scrutinize a different line and assume that me and my 23andMe second cousin match share more than one common ancestor.
DNAAdoption is a good site to look at. They have a methodology that is time consuming, but which they've had great success.
GenomeMate is an excellent utility that stores and analyzes matches across all platforms and is highly recommended.
Jeff Snavely's Chrome Browser is a must have for the Ancestry site. Jeff has included a download of all your matches ancestors, as well as the number of times an individual appears in your matches. For instance, my matches have 27 Elizabeth Smiths in their ancestor lines. So I added a column to the spreadsheet for spouse's surname and whether or not they match my mom. If I have 10 matches whose Elizabeth Smith's that married a Robert Jones and don't match my mom, I can then compare those trees and look for surnames common to other matches whose trees I've built out, like my 23andMe cousin or the several folks that all match me and my brother on the same segment on Chrome 13 (that tree is now up to 6000 individuals).
Again, this is time consuming, tedious and sometimes feels daunting, but at this point, short of having an original birth certificate with both birth parents identifying information, or hiring a genetic genealogist, it's pretty much the only way we are going to find candidates for our birth grandparents. On the other hand, I've read some pretty fascinating documents, and I enjoy the research.
The other thought I am pondering is combining all my research trees (I haven't yet worked out how to define myself as the home person, and my relationship to the matches.) taking a second DNA test at Ancestry and using it as bait to find DNA Circles and hints. This is sure to irritate some folks, so I would have to clearly identify the bait tree as a research intended to find my dad's birth parents.
Also, I've been paying a little more attention to ethnicity results. I know that this can vary across platforms, but since my mom's lines can mostly be traced to Germany and the British Isles, it appears that I'm getting my Viking blood from my Dad. And indeed, those matches that do not match my mom, appear to have much more Scandinavian admixtures than those that do match my mom.
Sorry for the long reply - I hope you found some value in it. Good luck and I hope to hear of your success!