Are there any others that are particularly effective?
Yes, if you know what wallet was used and if its transactions have distinguishing features. For example, multisig wallets usually use p2sh change, but the recipient rarely uses p2sh, which allows to determine the correct change output with high probability.
Data-Driven De-Anonymization in Bitcoin introduces two new general heuristics:
CONSUMER HEURISTIC. Consumer wallets only create transactions with two outputs. Therefore, if an output is spent by a transaction with 3 outputs it is not change.
OPTIMAL CHANGE HEURISTIC. The assumption is that wallet software does not spend outputs unnecessarily. Therefore the change value is smaller than any of the spent outputs.
Because if the change was larger than one output then this output would be left out and the change would be reduced by the output’s value.
The thesis also evaluates the effectiveness of the heuristics using data captured from Android Bitcoin Wallet with the Bloom filter address leak in late 2014.
It turns out that Multi-Input heuristic is by far the most effective: if applied to one address, in total 68.59% used addresses of the wallet are revealed.
By the way, the Heuristic 2 you mention was first described by Androulaki et al. in Evaluating User Privacy In Bitcoin.
Is it possible to bootstrap my clustering, for instance, maybe if some people have already associated a certain cluster with Kraken or Satoshi Dice, is this information available?
Blockchain.info has a database of tags (https://blockchain.info/tags).