I've found it in the 1901 census - document reference RG 13/733 f.29 p.27.
The enumerator recorded "The Victory" Gads Hill, Gillingham after no. 43 Gads Hill (licensed victualler: Arthur Henry A Hart - I think). Then came two buildings referred to as Victory Cotes (Cottages). Then 47, 49, 51 etc. Gads Hill.
Comparing the enumerator's route with an 1898 map on old-maps.co.uk and a modern Google map, I think the location of the pub would be on Pier Road near the corner with Dial Road.
Ruth