Alternative incentives for miners Currently the incentives for miners are the block-awards and transaction fees. Suppose I want to create a Bitcoin-like hash-chain for other purposes than storing coins (for example: storing messages), how could one create an incentive for miners to do the work?
Transaction fees, just like in the bitcoin blockchain.

The level of mining would then adjust up and down with the amount of usage.  You might need to subsidize it to get any participation from the start.

If demand is too low where fees don't justify this, then demand is too low where fees don't justify this.

Perhaps you can use Namecoin, which already exists, to solve your problem?  Namecoin can be used for namespaces other than just .bit domains.