Regarding finding his army records, if he had been in barracks it would have been an easy job to find a few officers in the census and search for them in the 1862 Army List and thus find the regiment. For men discharged in the regular army between 1855 and 1872, you need to know the regiment, as any papers that are held in Kew are filed in regimental order.
However, he is living at home. So he was either on leave, and those days leave (furlough) could be three months, so he could have travelled from almost anywhere. Or he was based at a local barracks, and his wife was not ‘on the strength’ ie they did not have married quarters in the barracks.
I have been through the 1862 Army List looking for a regiment stationed in Beverley. But I did not find one. I have checked a few of the census districts and there was a small barracks of East Yorkshire Militia - RG9/3568 Folio 12-13. These were part-timers, but there were usually a handful of experienced regulars on the ‘permanent staff’. So your John could be either a regular on leave; a regular (of an unknown regiment) attached to the EYM, or a member of the EYM.
I believe any militia records that survive are in class WO96 in Kew. But these are original records and you will have to visit Kew or employ a researcher to check in the at Yorkshire Militia.
If he was in the Militia, he was banned by law from serving abroad. If he was not described as an Army Pensioner in 1871, I would guess that he was a militiaman. If you do find his records it should clear up where he was born.
I cannot think of any wars in the 1860s. He could have joined the Militia from the age of 17 I believe, so even if he served from that age to just before the 1871 census, he would not have had enough service to qualify for a Long Service medal, which might have been another avenue to explore.
Ken