I can see a trailing top to the second digit in John's age on the 1851 census - I'm sure it says 15; however that may have been an error - deliberate or just an estimate. Looking at freebmd for the birth of a John Harding in Coldridge I can find Barnstaple Sep 1838 10-37, Sep 1839 10-38, Sep 1841 10-39, & 1 registered Tiverton Sep 1843 10 -249. My knowledge of Devon geography is not good enough to know where a Coldridge birth would be registered!! I have no doubt, from previous experience, that people were able to lie by 5 years or so at marriage - he may have lied at army enlistment although men ususally added to their ages, not take it away!!! - so had to keep up the pretence. How old was he said to be when he died?
I cannot find a marriage of a Faith to a Samuel Harding on freebmd Sep 1837 onwards, but they probably married before then. I couldn't find it on Pallot either [on ancestry] but that may not be comprehensive. I suggest you try an Online Parish Clerk for Devon [find them by googling]; these are wonderful volunteers, and even if records are not available online, the OPC will look records up for you.
As far as the whereabouts of the 19th - there is a very good Armed Forces board on this site; also a yahoo group 'britregiments' both full of knowledgeable & helpful people [britregiments is not for genealogical queries, but they will help will regimental movements and resources].
Unfortunately as John died in service, I don't think [although perhaps someone can correct me] that his military record will be at the Public Record Office at Kew. But if you could get hold of that, it would help greatly to tie your information together. I read that the Green Howards enlisted much in Yorkshire, but I am sure roving enlistment sergeants would have got all over England.
Hope this helps, Josey