It depends on the definition of scaling, computational scaling is limited and favours sharding of contexts then maybe use zk proofs to settle between contexts. But data availability isn't doomed, it is actually possible to scale it with users, as long as the number of users is actually objective, which is the real challenge. If you KNOW that there are 10X more users now than last year, then you can tolerate 10X more data in a data availability sampling paradigm. Which is why Celestia needs to hardcode the number of clients the community believes there are around the world.

But I wonder if someone can use Proof Of Work as a proxy of how many users there are watching the chain and sampling chunks of the data.

I don't mean necessarily decentralised mining, but just using the hashrate as a proxy for demand, and demand as a proxy for the light clients taking data availability samples...

This is not something you can do in celestia without oracles of the token price, but we have hashrate and they don't.