I know you have your heart set on velvet but there are some nice colours in felted wool that would work well for appliqué. If you can't find felted wool you like, you might be able to do it yourself with some wool sweaters from the second hand store.