Have you seen him on the
Florida State 1945 or 1935 census? You can browse the images only at
http://search.labs.familysearch.org/recordsearch/start.html#... so you'd have to know where he was in 1935/1945. Would seeing him in the city directories be helpful? Have you searched for him at Ancestry.com? If you don't have a subscription, you could still get an idea of where he might have been by the search results. Alternately, you could search Ancestry.com Library Edition at a library. Depending on where you are, you might want to check with the library first, to see if they subscribe to Ancestry. Ancestry has digital images of WWI and WWII draft registration cards.
Have you thought about obtaining his birth certificate? You could find out the names of his parents and possibly his siblings and get information about him that way.
Have you also tried searching for him at WorldConnect at
http://wc.rootsweb.ancestry.com/cgi-bin/igm.cgi? Perhaps someone else has researched his family and listed him.
It sounds like you have already done a lot, so I hope some of this helps.
Bonnie