I lived in Hall’s Creek for 7 months in 1995 and did a lot of climbing in the area. Moola Boola Station has good red granite. It is now aboriginal land. You might get permission. Sawtooth Gorge has red sandstone and it was public land. I bouldered on the ancient reef that pops up near there as well, and did some routes out at Yihli Station on top rope. Same stuff, much taller. Again aboriginal land. Mount Pierre Staion has amazing pinnacles of the same ancient reef popping up out of the ground. There’s some granite slabs on public land facing Argyle Mine turn off, but on the other side of the main road. Purnululu is out as the beehive shaped formations are very soft. There is some solid rock in the park, but I never got there and I don’t know if you’d get permission. Apparently there’s some climbing in Kununurra, but I never got a chance to climb there.
The problem you have is not a lack of rock, but access. A lot of it is on stations or aboriginal land. I climbed with a doctor in the AMS which helped a lot, and it was 1995 and people weren’t scared witless about being sued.
A fair bit of some of the cliffs and gorges is like loose stacked bricks. I backed off a climb in one gorge when I realized any piece of gear I placed would just blow the bricks apart if I fell.