Hello John,
The answer to all this will be in his service record, if it has survived, and that will reside at the National Archives, Kew. Until then we can only guess, or go on the very limited evidence which all seems to come from his marriage certificate and his death, kindly supplied by Margaret and manmack. I guess you don't have his birth (about 1845-46?).
The children you mention at Winchester - I think, and I'm not an expert, that Winchester was one of the depots for the King's Royal Rifles. As to when Harry joined up, it would depend, but most men joined the army at about 19 or 20 or so, so perhaps the mid 1860s.
The 2nd King's were in Ireland in 1866, India 1867, Afghanistan 1878, India 1880, to South Africa in 1881, then England (Davenport) 1882, so this would tie in with a marriage in that year. They were in Ireland again 1888 (Enniskillen), Gibraltar 1891, Malta 1895, Natal 1897 and the second Boer War in 1899. If he did join in the 1860s, that's long service.
To find him on a UK census domestically, you'd have to check the 1851 and 61 census returns. By 1871 he was probably in India (unless he was a later draft). Some wives did go out with the army (one married man per 12 infantrymen), and he could well have married and had his children in India. No wives went on campaign in Afghanistan after the disasters of the first Afghan War, but they would have remained at the depots (I think Mirat for the KRRC), as many did. Fever took a few of these too. Did Charlotte have an unusual surname? It was not uncommon for a soldier to return to England and marry a comrade's sister, or even wife if his comrade died in service, and it might be worth checking the medal roll for her surname, just in case, though it won't be conclusive.
These are just some ideas, and I'm mainly going on the experience of a few other soldiers' stories, which may not mean much!