If you really can't make anything to send him, you could make a donation to a worthy cause for him, like to PETA or the Humane Society, or to Slow Food (www.slowfoodusa.org
), etc. He sounds pretty conscientious, so I'm sure he would appreciate something like that.
Maybe you could make something for him at a cat-free friend's house? I second the stencil ideas-- those are always so simple and versatile! And i love the idea of a personalized yoga mat bag.
You could also send him a In-a-box type gift that is themed around local foods where you live-- you know, like more herbs/canned foods grown by you or other local people, local honey, regional recipes, etc.