Ironically, the better you are at reducing your waste, the less likely you are to succeed at replacing plastic bags for the irreducible portion. My mother throws out actual garbage twice a year - one small plastic bag such as the ones you get from grocery stores, every 6 months. While she always has a reusable shopping bag in her purse, she finds that plastic bags come into her house anyway - for example people bring things over in a plastic bag and leave it - so she uses one of these waifs and strays to accumulate 6 months of garbage.
Newspapers, which could be used to wrap messy garbage so you don't need plastic, are better put into the recycling to be turned into other paper - and better still declined and read online. Jars and tins which could hold messy garbage are better put into the recycling also. Where I live we can recycle tetrapacks (I know this is rare) and film plastic, and she saves these (rinsed) and brings them to us when she visits, so they can be recycled. She lives in a city with a "green bin" program so all food waste and other nasty stuff goes into the green bin, which insists on very specific bags being used. Foil, Styrofoam and such are also recycled. Egg cartons and rubber bands she also brings to us, and we give them to our farmer, who uses them to wrap up other people's vegetables, eggs etc.
Most importantly she's quite rabid about what she buys. She has completely stopped buying certain things she quite enjoys, because of the packaging they come in.
Her actual garbage typically consists of some potato chip bags, wax paper, and other inert-but-not-recyclable materials that don't need to be in a plastic bag. She just uses one because that shows people that it's actually garbage. I would suggest to you that reducing the total amount of garbage you produce in this way is a much bigger contribution to sustainability than changing what you put your garbage in.