I recommend acrylic paint as well. If you get the good kind, which isn't runny, and rather thick, such as Reeve's acrylic paint, it works very well in getting a solid color and it easy to brush onto things like shoes. One coat is actually enough, but if you're feeling ambitious you can try for two for a REALLY solid color. :3
I painted my Miku shoes blue with the Reeve's acrylic paint and I've worn them in the rain and such and nothing's happened to them so far. ^^
Every time I look back on my signature,
I somehow get embarrassed.