What is a bottle of shoe shine anyway? Shoe polish I have seen comes in a little tin. Like this. A shoe polish tin looks an awfully lot like a chewing tobacco tin. Is this what the guy had (or at least a plastic version)? Disgusting habit, but certainly not prohibited.

By the way, kudos to the CATSA guy for ignoring the OP.