If you can't add a separate field, just add a log table.
Don't optimize for fictional requirements that haven't surfaced, and don't add shortcuts.
EDIT: Let me clarify my point here. A timestamp is just a timestamp. Giving a timestamp a role on signifying the state of an entity is a semantic shortcut, and semantic shortcuts lead to problems. I believe that DB structures should be as clear as possible. For example, it's impossible to know whether a timestamp is the authority on an entity's state by looking at a table structure. But a boolean field like "is_deleted" or "deleted" doesn't have that problem.