How to add a check constraint in Postgres without locking the table?

You can create a NOT VALID CHECK constraint, which will enforce the constraint going forward, but will not check the entire table for validation upon creation. At some later date, you can attempt to VALIDATE the constraint (when a lock on the table is ok)

Please review the documentation - Quote below:

ADD table_constraint [ NOT VALID ]

This form adds a new constraint to a table using the same syntax as CREATE TABLE, plus the option NOT VALID, which is currently only allowed for foreign key and CHECK constraints. If the constraint is marked NOT VALID, the potentially-lengthy initial check to verify that all rows in the table satisfy the constraint is skipped. The constraint will still be enforced against subsequent inserts or updates (that is, they'll fail unless there is a matching row in the referenced table, in the case of foreign keys; and they'll fail unless the new row matches the specified check constraints). But the database will not assume that the constraint holds for all rows in the table, until it is validated by using the VALIDATE CONSTRAINT option.

(Not enough rep to comment on the other answer)

It's not clear from the phrasing in the accepted answer what "when a lock on the table is ok" means.

According to Postgres ALTER TABLE docs:

VALIDATE CONSTRAINT grabs a SHARE UPDATE EXCLUSIVE on the altered table,

and from the Locking docs

SHARE UPDATE EXCLUSIVE allows other concurrent transactions to get a ROW EXCLUSIVE lock (which is used by INSERT, UPDATE, DELETE), and SELECT is allowed with any lock-type besides ACCESS EXCLUSIVE.

Meaning - "reads/writes" will not be blocked when running VALIDATE CONSTRAINT - you don't need to "wait until it's ok to lock the table".