I can't find this guy anywhere in any of the sites I have searched, and I've searched a lot.
He is in my tree as a memory from my Grandma (it's her father) but there is no proof of him anywhere.
Genealogy & Family History Stack Exchange is a question and answer site for expert genealogists and people interested in genealogy or family history. It only takes a minute to sign up.Sign up to join this community
Without knowing where you've searched -- and more importantly, how you've searched -- it is difficult to give much more than a general answer. I encourage you to read any search tips and to watch whatever tutorial videos may be available for each site you search on. It is generally better to do a wide search first and then to add more details to narrow the results. You should be aware that your ancestor's name may not be spelled exactly as you expect it to be. For one of the people in my husband's family, her name is not in the birth records -- I was only able to find her record because I looked for all the children of the same parents (which I realize you can't do, if you don't know the parents' names). I suspect it is the right family because the birth is about the right time, and the street address matches many other records I have for that family.
If you can't find the birth record itself, you may be able to find other records that have the birthdate in it. The checkist Sources of Genealogical Information is US-centric, but it illustrates the principle that you can find information in records which might not seem to directly answer your research question.
Here are some research guides for finding someone's birth in Scotland:
For finding other records, see:
Discover Your Family History from SCAN (Scottish Archive Network)
Trace Your Ancestors in Scotland from Glasgow Guide (this guide contains information about the Glasgow City Archives)
Lanarkshire resources from HappyHaggis
Scotland from CoraWeb
FamilySearch's British Isles Team have produced online webinars about doing research in Scotland, the most recent from April and May of 2015. The recordings and handouts can be accessed via the Wiki page Online Webinars from the British Isles Team. Much of the material is for the periods before the 20th Century, but the webinars on Scotland Websites might be useful to find resources you've missed.
You don't say where your great-grandfather might have been in 1939, but if he was in the United Kingdom, you might be able to find him in the 1939 National Identity Register. The enumeration was carried out on 29 September 1939 and was the start of the records for the National Health Service. The National Archives of Scotland's website has recently been renamed as The National Records of Scotland. If you know when your great-grandfather died, you may be able to order an abstract of the information on that records. See the NRS's research guide for National Registration.