A minor niggle.
Just because they were married by the Free Kirk minister does not suggest that the wedding ceremony was held in the church building. The majority of marriages at that time took place elsewhere. The traditional place was the bride's home, but if she had no parents, or was married a long way from home, the ceremony was often performed in her employer's house, or in the manse.
You are indeed very lucky that the Church of Scotland clerk recorded the marriage in the C of S records. This was supposed to be the norm, but unfortunately there are many examples of marriages, and baptisms, going unrecorded.
As for John's parents, at least you now know that he was born in the parish of Cromdale Inverallan and Advie, and that (assuming his age in the census is correct) he was born in 1830 or 1831.
There is only one John Fraser in the index to baptisms in Cromdale Inverallan and Advie between 1829 and 1832. This is the son of Donald Fraser and Marjory McGrigor, who was born on 21 October 1831 and would therefore have been aged 9 on the date of the 1841 census. However he is with his parents at Corshellach in the 1851 census, therefore he is not your John Fraser. (This family seems to be missing from the 1841 census, at least on FreeCEN.)
There are three John Frasers in the 1841 of approximately the right age.
One aged 9, in the household of Alexander Fraser at Wester Achnafairn, where is also an Alexander Fraser, aged 11.
One aged 10, in the household of Donald Gordon at Bynaballich.
One aged 11, in the Orphan Hospital, where there are also James Fraser, 12, and Margaret Fraser, 10.
If the ages of all the John Frasers in the 1841 and 1851 censuses are accurate, yours would be either the second or the third one, or just possibly another one altogether, born in Cromdale but moved to another parish by 1841, though I have not found a likely candidate.
The only suggestion I have is to contact the Highland Genealogy Centre in Inverness, and ask them if there is any record in either the Kirk Session or the Parochial Board records of Cromdale Inverallan and Advie, or any records of the Orphan Hospital, that might shed any light on your John's origins.
It doesn't help that some parts of Cromdale Inverallan and Advie are in Moray, and some in Inverness-shire, and that people born in that parish might say their place of birth was any one of those three parts of the parish, or indeed Grantown-on-Spey.