Two answers to this I have seen about:
1) get your local green party involved, our local shops have picked up the "green" branding and charge 1p per bag.
2) the co-op some time ago introduced biodegradable carrier bags, made of some sort of paper, but was just like your normal carrier bag. Having tested it though (left it in some moving boxes for three months), it does slowly disintegrate into little papery shreds, so you could put it in the compost heap!
3) if this is too complicated, how about standard brown paper bags for small purchases? maybe with little carrier holes? They break down better/are more easily recyclable than plastic...