If it's the leather-like synthetic, I'd suggest trying a leather paint. It's flexible, so it doesn't crack on shoes, and permanent (on leather, at least, but I imagine on vinyl, too). I use Angelus brand, which says it's for leather and vinyl. It covers beautifully, though you'll need a few coats if you're going dark to light. For an example look at my Korra costume. There are three armbands, all are painted with Angelus paint. One was dark red leather, one was white, and one was dark brown. All were given a white basecoat first, and they looked like they were the same leather.
I like to get mine from here: http://www.dharmatrading.com/html/eng/10144517-AA.shtml
Always incredibly fast shipping and good customer service.