Suppose I store a random salt value for each user. Do I have to generate a new salt value when that user password is changed or do I use the same value for the whole lifetime of that user account?
You should change the salt. The salt is designed to be unique (as most as possible) for all password instances.
If you use the same salt for the old and the new password, then an attacker who sees the old hashed password and the new hashed password can attack both for a cost which is less than twice the cost of attacking one. This is exactly the kind of thing that the salt was designed to avoid (and the salt has no other usage than that).
Of course, the old password, being old, is no longer a valid way to enter your system, but since users tend to reuse passwords, the old password might still be worthwhile (from the attacker point of view). In particular, the user may reuse that old password when he will change his password again (this is what most users do when faced with a system which requires regular password changing: they alternate between two passwords).