Now I just have two indices. One that indexes only hot tuples, it's very heavily queried and works blazingly fast, and one that indexes by (hotness, key). I include the hotness value on the query, and still works quite fast enough. Luckily, I know things become cold after an update to mark them cold, so I can do that. I included hotness on the index to cluster updates on the hot part of the index, but I could have just used a regular index and paid a small price on the updates.
Indeed, for a while it worked without the hotness, and there was no significant trouble. I later found out that WAL bandwidth was noticeably decreased when I added that hotness column, so I did, helps a bit with replication. Has worked ever since.
I'm surprised that clustering updates into the hot part of the index, without also clustering them it into a hot part of the table heap, works well enough to make a difference. Does clustering in the table just come naturally under your usage patterns?