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.
-Erica