Have you seen the padded order-based coloring scheme worked out here?

https://github.com/bitcoinx/colored-coin-tools/wiki/colored_coins_intro

Just to clarify, a variant of padded order-based coloring called epobc is already implemented in coloredcoinlib (which is used by ngcccbase/ChromaWallet). It isn't document yet, however.
The idea is to use the otherwise unused nSequence field of first input to specify padding and differentiate between genesis and transfer transactions.
Padding can be chosen for each transaction individually and can be set to zero. 

Python code is here (I recommend waiting for documentation, though):  

https://github.com/bitcoinx/ngcccbase/blob/master/coloredcoinlib/colordef.py#L262

It is able to work with transactions with multiple colored and uncolored outputs, particularly, p2ptrade transactions.

Examples of p2ptrade transactions on mainnet:
https://blockchain.info/tx/8c1926f2e3527153bf06e8ab2c8a417aad3d8e6cd993a4350efbb4050ab961fa
https://blockchain.info/tx/f85b6213939c9cbc14538dd24838061179cac2485f50be20a974b819a85e5ee9 (It looks quite a bit weird, I know.)