Yes a Birth certificate would settle the matter completely!
The Army records would seem to be for a different Henry altogether, who was as mentioned born Portsea 1860.
His father could be Henry Eade of Petersfield who married Mary Ann Clarke at Portsea in 1856.
(He was the Henry who died at Portsea Asylum in 1881 - incidentally another brother died at Woking Asylum, one committed suicide at Dorking and their mother died of mental problems at Petersfield - happy household that!)
I had a look at the area that Henry and Mary Ann inhabited at Portsea and it was none too good. Henry was working as a Gardener Journeyman, a family trade at that time, and so were probably pretty impoverished.
If Henry the Soldier was their son, I would not be surprised at all if he wasn't baptised, or despite the prevailing penalties; that they didn't bother to register him either.