Apart from buying things? I'd think that helping people discover shops would be tops. Leave positive Yelp & Google reviews, tell everyone you know about the shop.
Beyond your good suggestions of leaving good reviews and telling others, I'd suggest buying gift cards from these shops for people you need presents for, thus forcing them to patronize the shop at least once and upping the chances the store gets another regular.
He doesn't like "stuff", but he's frugal and otherwise won't spend straight up cash on himself. Goes straight into savings.
I would never dream of getting him a gift card to help a shop, though. I get him gift cards for things I think he will enjoy but is too disciplined to spend money on for himself otherwise. It's actually a nice way to force myself to really think about him and "give an experience". Or, when I can't, some decent wings and a beer.
My idea of a good gift is something that a person wants, but can't justify buying it to themselves.
You could say that that's worth less to them than the equivalent amount of cash since they didn't make that trade, but it definitely doesn't end up feeling that way as the recipient.