I haven't tried it, but was told by a local guy with lots of rocket stove/natural building experience that yes it will work. The sawdust will burn, leaving lots of little airspace, which is great for insulation. Another option is perlite, although obviously more expensive
You mentioned that the saw dust is intended for your cob bench, actually the straw in the cob is not for insulation but for structure. Like fiber glass cloth in resin the straw works to hold the cob together. Maybe a better example would be steel mesh or rebar in concrete. Another thing is that you would not want to insulate the bench you want it to radiate heat out to your room, and cob with the straw as reinforcement works great for that.
I can't say for sure but about any kind of mesh material like an old lace curtain or fish net like material would work but I'm no expert so others may have better suggestions.
Vern's got the right idea - you only need insulation around the firebox and the heat riser areas (which perlite will do better for you, or rock wool). The bench doesn't need straw in it if you can't get it, it can be solid aggregate (sand/gravel/rubble) with just enough clay to hold it together. If it was a wall, the straw would be hugely important for tensile strength, but as it's just sitting on the floor it won't have much in the way of wind load, nor can it fall on anyone.
If you want a tougher, more crack-resistant surface in the top layers, any natural fiber will work. I avoid synthetics because the heat might possibly melt them, plus they don't biodegrade. But anything like dried grass, 'oakum' (shredded natural rope), coir matting fibers, pet hair, horse hair, barbershop floor sweepings.... it's all fiber.
Long shreds of sawdust e.g. planer curls can be useful, but itty bitty sawdust grains just work as insulation and aggregate (no different structurally than the sand / mineral soils).
Fine sawdust powder is useful to make Vernacular Insulative Ceramic (that is, your own cast-in-place clay-slip-and-burnable-stuff insulation foam). There was a project in Uganda that used charcoal dust for this purpose. They formed the bricks from a mix of clay and combustible dust, then heated them quite hot to burn out the dust before using the bricks. Not all the charcoal burned out, but the insulation worked. If you don't care about how long it keeps smoking, you can burn out a VIC heat riser in place.