If that's feasible, shouldn't Postgres do it automatically when adding that constraint (perhaps optionally, denoted by something like CONCURRENTLY)? Where's the catch?
All that NOT VALID does is add the validation for inserts and updates but does not check the existing data. This does let it get away with a less restrictive level of locking.
However there may be data which is not valid for a long long time, the "concurrently" query could be running forever.