Tracking a line of John Smith's when I have no clue as to where they were born

My three and four times great grandfathers are both called John Smith. My 3 times great grandfather appears in the marriage records of St Mary's Church, Kingsclere, Hampshire in 1813, when he marries Elizabeth Rogers. John is said to have been born in 1786, but does not appear as far as I can tell, in any baptismal records in the area. Both John and Elizabeth were said to be from 'out of parish'. They settled in Kingsclere and had their children there. John was a labourer, but became a tenant farmer of 100 or so acres. Their eldest child, Richard stayed in Kingsclere and took over his father's holding on John's death. The youngest son George (b 1820) went into the Royal Artillery and through various turns of fate ended up a lieutenant in the Osmanli Horse Artillery, a regiment raised in the late 1840's to fight for the Turks in the Crimean War. He was released from service on a pension in 1856 and moved to Cornwall where he married Eliza Richards in 1856 and died, three children later, in 1860. His wife and children were then living of his pension.
My challenge is in trying to track back the John Smith's to their places of birth. It appears impossible to a novice like me.
Any thoughts?