Ok, so he's listed as a soldier in 1858 then?
Key is going to be to find his regiment. First thing to do is widen out from that date, so 1851/61 censuses, childrens birth certificates etc. What do they say? Sometimes you'll be lucky and find they give more detail than just "soldier".
He's listed as deceased by what year? So work back and see if you can find a death that matches.
Where and when was he born? Might get lucky and find service papers for him based on that alone.