To dye or not to dye, that is the question.

I think I would give the RIT product a try. There definition of color-fast and what you are looking for may be the same. Just make sure you try it some where that normally won't contact your closes to make sure it won't won't mark them.

I don't think SEM will work well. I have had very good luck with SEM dye on vinyl but I tried it on a fabric seat and it wore off pretty quickly.

Otherwise you are going to have to use one of your other options. And don't forget your local pick-n-pull junk yard. I wouldn't be suprised if they didn't charge you at all if you harvested some belt webing.