The routing decision is done after OUTPUT chains in both nat and mangle tables, and before POSTROUTING of course. Is this what you meant?
Ah, so for the output path, I need to use "-t mangle -A OUTPUT" instead of "-A PREROUTING"? I just need to add the extra rule, then.