In short, IBM integration bus can do it in a message flow... But let me provide a WMQ Java answer also:
The message object that is received can be modified and sent back ... All you need to do is to read all the stuff you need from that message to some java object. For example you can use a Map for Properties. Then call clearProperties() and then set the modified properties. The issue of readonly goes away after calling clearProperties() (http://docs.oracle.com/javaee/5/api/javax/jms/Message.html#clearProperties%28%29)
So a mix of (2) and (3) can help in solving the problem.