Inside MessageListener I throw exception. Default behaviour of message listener container is requeue message. My question - is it possible to change message headers when message was requeued?
No, you cannot change a rejected message; you would have to publish a new message after the exception instead of rejecting it.
The framework provides a mechanism to do that using a RepublishMessageRecoverer, adding headers including the stack trace, but it doesn't let you add your own headers; you would need to subclass it to do that.