Cluster command locking read only queries on replica I noticed that clustering can take a long time and lock the table entirely, even for reads.

Index Organized Tables and incremental clustering would be perfect, but sadly they aren't supported by PostgreSQL.

Now I realize that it also lock the replicas' tables, so apparently there isn't a way to cluster without having a lot of downtime?

Setting rds.logical_replication to 1 on both master and replica instances didn't help.

I would like to cluster four big tables every week for better performance.
A problem with letting queries operate against the table while it is being CLUSTERED (or VACUUM FULL) is that even queries which are select-only from the user's perspective can still write to the table in non-user-visible ways, to set hint bits and clean up after rolled-back transactions, for example.

You could set up two replicas, one which has replay paused just before the table cluster operation starts and so is open for readers during the CLUSTER, and another which is allowed to replay normally.  Then once the CLUSTER is done, everyone switches from the paused replica to the other one, so that the paused one can catch up.  Whether you can tolerate using a replica which has fallen behind by hours is another question, though.

There are projects that will do online clustering of tables, such as pg_reorg and pg_repack. They are not part of the PostgreSQL core, but they are probably worth a look.  I have not used them in production, but mostly because I don't have a production need for them.

Yet another option would be to partition the tables.  Then each partition can be reclustered separately, and you might not have to do clustering at all if the partition constraints accomplish the same thing as clustering does--generating more efficient IO patterns for partial scans.