So far, using colored coins seems to be my best bet, but I'm wondering if certain things are possible:
It's worth noting that colored coins concept is fairly general, it can be customized for a specific application.
It's not just "what chromawallet can do". ChromaWallet is just one of applications.
1. Can an issuer color coins that don't belong to him?
Yes. Color exists only as a client-side configuration, so you can just add a new definition.
(This isn't true for all implementations of colored coins, say, BitcoinX specification requires a particular format of a genesis transaction. But chromawallet/chromatoken implementation is very flexible.)
It would be very inconvenient for the other person to have to return the coal to me in order for me to light it on fire.
Well, that can be implemented as a special kind of transaction, similar to how p2ptrade works. But you gotta pay a fee for that. If you're talking about cheap-ass assets, it's better to avoid fees...
2. How long can a moniker be,
Monikers exist only on client simply for convenience. They can be arbitrarily long, but you probably want a custom asset definition format, there is no need to stuff all the information into the moniker.
and do I need to worry about spamming the blockchain if I make 10,000 different colors?
Each particular colored coin is a separate transaction output. 10000 doesn't sound like a large number...
and it might potentially mean a separate color for each and every of the 10,000 different pieces of coal in my application.
People usually call this approach (separate color for each individual thing) it 'smart property' or 'transferable virtual property'. See here:
https://en.bitcoin.it/wiki/Contracts3. Is it possible for me to determine the order that colors were added to a satoshi?
Depends on how you introduce these colors...
Additionally, bitcoin's transaction fee is currently way too expensive for my application. I can't justify selling pieces of coal that only have uses inside my application at 0.0001 btc each when the transaction fee is another 0.0001 btc. This would be easily fixed by my using a cryptocurrency with a cheaper fee. Are there any plans to develop a version of ChromaWallet that can work with other cryptocurrencies?
Yes, but you should consider other options, like something not based on blockchains... OpenTransactions, maybe?
You'll have to run your own server, but transactions can be free, I think. I have no idea how hard is it to customize it, though.