Great idea to find other "currencies" from your clients/suppliers. What about the idea of having teachers provide you with free classes as their way of paying? You could then turn those freebies into promos/giveaways, etc..
The problem with teacher paying with free classes is that many of the free classes are just ways to get a first meeting with a customer. And then future transactions between the student and the teacher happen without TeachStreet being part of them. But, we're experimenting with some ideas in this space (helping teachers to offer promotional pricing, with additional featuring on TeachStreet.com itself).