How to properly and effective rename a vaue (column) of a foreign key in both tables?
I would consider using a code for the status. I.e
CREATE TABLE USER_STATUS
( STATUS_CODE CHAR(?) NOT NULL PRIMARY KEY
, STATUS_NAME TEXT NOT NULL UNIQUE
);

The use of char is discouraged by the postgres community, so an alternative would be to use text and an additional constraint:
CREATE TABLE USER_STATUS
( STATUS_CODE TEXT NOT NULL PRIMARY KEY
, STATUS_NAME TEXT NOT NULL UNIQUE
,     CHECK (LENGTH(STATUS_CODE) &lt;= ?)
);

It should be more stable than the name, but more intuitive than an int.
But for your question, I would probably insert the new value:
INSERT INTO USER_STATUS (NAME) VALUES ('Valid');

then update all users:
UPDATE USERS SET STATUS = 'Valid' WHERE STATUS = *Normal';

and finally, remove the old status:
DELETE FROM USER_STATUS WHERE NAME = 'Normal';

For the more general case where there is a hierarchy of tables involved, you traverse them in DFS and insert new rows on the way down. When you reach a leaf you can use update and then delete rows as you climb the tree back up. You can use INFORMATION_SCHEMA.REFERENTIAL_CONSTRAINTS to obtain the edges in the tree, and then use for example a topological sort to determine the ordering of the tables.
Another advice is to stick with the same name for the attribute throughout the model. I.e:
CREATE TABLE USER_STATUS
( STATUS_CODE ... NOT NULL PRIMARY KEY
, STATUS_NAME TEXT NOT NULL UNIQUE
);

CREATE TABLE USERS
( ...
, STATUS_CODE ... REFERENCES USER_STATUS (STATUS_CODE)
...
);