OK, let's summarise what we know already.
I am assuming that everything in the records is accurate, and no -one was lying about their birthplace, parents' names or marital status. My comments, questions and suggestions in italics.
John Barr was born 1852/1853 in Paisley. You presumably know from his marriage certificate what the names of his parents were.
Mary Buchanan Newlands was born in Paisley on 1 May 1855, parents John B Newlands and Jacobina Oliver.
John Barr and Mary Buchanan Newlands were married in Paisley in 1879.
Norman Stirrat Barr was born in Kilmarnock on 19 March 1881.
1881 Census details from LDS transcription
28 Clark Street, Kilmarnock, Ayrshire
John Barr, Head, Mar, 28, Engineer master, born Paisly, Renfrewshire
Mary B Barr, Wife, Mar, 23, born Paisly, Renfrewshire (Mary lied; she was actually 25 not 23)
Norman S Barr, Son, 1 month, born Kilmk, Ayrshire
Cathleen Newlands Barr was born in Kilmarnock on 20 March 1884. Therefore John Barr must have been alive in June 1883.
In 1884 John Barr, engineer, Kilmarnock, was bankrupted.
1891 Census: Mossgrove King Street Helensburgh Dunbartonshire
J B Newlands 67
J Newlands 62
J Newlands 44
N Barr 10
K Barr 7
Compare this with the 1881 Census: Burn Bank Cottage, Calside, Paisley, Renfrewshire
John B Newlands, Head, Mar, 57, Watch & jeweller, born Bathgate, West Lothian
Jacobina Orr, Wife, Mar, 52, born Paisley, Renfrewshire
Jacobina Newlands, Daughter, Unm, 34, born Paisley, Renfrewshire
So in 1891, 10-year-old Norman and 6-year-old Cathleen/Kathleen Barr are living with their maternal grandparents
On 22 December 1893 Henry Gee, born 1852 in Gloucestershire, parents Joseph Benson Gee and Elizabeth Bellamy, marries Mary Newlands Barr, widow, born 1857, parents John Buchanan Newlands and Jacobine Ovor. (Mary does appear to have lied about her DoB again - she was born in 1855)
Norman S Barr, aged 13, arrives in USA 31 July 1894.
1900 Census: Tombstone, Cochise, Arizona Territory
Henry M Gee 47 Born October 1852 England. Mine owner.
Mary Gee 41 born May 1859 Scotland. Had 3 children and 3survive. Maarried 1894.
Kathleen Gee (the name Barr was crossed out) 16 born May 1884 Scotland. Step-daughter
Kathleen Newlands Barr, born 1884, arrives in USA, mother Mrs Henry Gee, Arizona.
Have you considered the possibility that after his failure in business, and perhaps struggling for a while, John and Mary left the children with her parents and travelled together to the USA to start a new life, intending to send for the children once they had settled. John died in the USA before they had achieved this, and Mary subsequently married Henry Gee, moving soon afterwards to Tombstone, Arizona. They sent for the children, and Norman arrived soon afterwards. Kathleen must also have travelled to USA because she was with her mother and stepfather in 1900.
If so, then you are looking for John's death in the USA, perhaps New York, because that was where Mary married Henry Gee. Why not try searching for a death in the USA using the parent names John must have given on his marriage certificate in 1879?