>Are cats actually effective at pest control or is that cat propaganda?

Yes. Have you never heard of a barn cat? Until recently pretty much ever commercial or industrial facility large enough to have its own maintenance department typically had one or more.

>How would cats operate in these societies?

Just like a barn cat. Leave out starvation rations for it and it'll hunt for the rest.