Hi Sangal
Records are filed according to date of discharge. Those discharged 1883 to 1913 are filed alphabetically, so you do not need to know his regiment to search for his record. They are original documents in Kew, but if you cannot go there, Findmypast are putting them online 'by 2011'.
You should also search the overseas/regimental BMDs on Findmypast as the regiment should be given in the index.
It might be ASC, or RAMC - or it might be part of the address. Can you post a scan of this bit?
Ken