No record found in the GRO index to either army or regimental returns of births/baptisms or marriages under the names you gave.
As there is uncertainty as to how and where he met his wife, I believe to progress further you need to establish how and where he took his discharge from the 21st Regiment of Foot. As there is no preserved pension record for him the only way of doing that is using what records there are for the 21st Foot in the National Archives, Kew. At least then you will have some factual baseline to work from and maybe establish his origins.
The ideal records would be regimental casualty returns that record men becoming ineffective i.e.
sick, wounded, transferred, discharged, deserted and died; if they exist they will be in document series WO25.
The only other records are Muster Books and Pay Lists, some are quarterly others monthly, the last entry for a soldier should give how and where he was discharged; Musters are in document series WO12.
An advanced search of the new Discovery catalogue at http://www.nationalarchives.gov.uk/
for records of the 21st[and 21] Foot 1851-1864 revealed:
There doesn’t appear to be any surviving casualty returns for the regiment’s 1st battalion, at least not indexed. All there is in the catalogue is:
WO 25/3365 Index to Casualty Returns: 21 Foot 1 and 2 Battns.:
Dates 01 January 1850 - 31 December 1910
I don’t know what information the index contains.
Muster Books & Pay Lists
These for the whole of his service so it should be possible to track backwards from his service in the Crimea (for the 1st Batt, 21st Foot present 1854- 1855) to his enlistment and forwards to from the Crimea to his discharge, and if you are lucky his place of birth may be recorded as well as mention of his marriage, the ones of possible interest to you are:
WO12/3819 21st Foot 1st Battalion: 01 January 1850 - 31 December 1851 to WO 12/3832 21st Foot 1st Battalion: 01 January 1863 - 31 December 1864
Professional researchers will charge an hourly rate to check those records, some start at around £25 GBP per hour, plus copies and for the period you are looking at it shouldn’t take more than a couple of hours.
I have no links to any researchers, but you will find a list of those specialising in military records at Kew via the NA’s web site at http://www.nationalarchives.gov.uk/records/paid_research.htm
or use your browser to search for – military research online – and you should quickly find one specialising in Military records at Kew.
If you decide to go down the researcher route, try to give as much information as you know as clearly as possible and define the limits of what you want and request an estimate. Also Kew now permits digital photography of their records so ask if digital images are available of relevant documents.
By the way, in your original post you mentioned, “stated he received two silver medals”, one was the Crimea Medal, to check what the other was search UK, Military Campaign Medal and Award Rolls, 1793-1949 on Ancestry for his entries.