You can seal the shoe polish with a clearcoat but test it first as it may haze.
If you want a permanent finish look up Mohawk wood toners in rattle cans. Generally rubber props such as a baseball bat are cast in a neutral color as the base. Sometimes the base color is dark, sometimes light, sometimes black... A mix of prosaide and latex paint can be used as a base as well which also adds some texture. Just brush it on, less is more as you want the base tone of the actual rubber to show for that color depth. Once thats hit and dried with a heat gun, just spray on the Mohawk toner in light coats, heat gun inbetween coats, alternate colors, heat gun... It actually only takes about five minutes to paint a rubber bat to match a hero prop when you get it down.
You can also email the seller directly and see if they can paint it more to what youre after. Never hurts to ask and could possibly be cheaper to pay a few dollars more than invest in cans of Mohawk.
This is a rubber log from one of the Zorro films, base was black rubber, generic tone for the color as it would get dirt and moss and other such and what nots applied to it with some hair spray to come off when being swung and hitting someone. This rubber log is about 15 years old and has been used a dozen times since for an idea of how durable the above application and material methods are.
