Why are InnoDB's index keys limited to 767 bytes?
This seems to be linked to the size of the InnoDB pages:


  If you reduce the InnoDB page size to 8KB or 4KB by specifying the innodb_page_size option when creating the MySQL instance, the maximum length of the index key is lowered proportionally, based on the limit of 3072 bytes for a 16KB page size. That is, the maximum index key length is 1536 bytes when the page size is 8KB, and 768 bytes when the page size is 4KB.


Thanks to XL on the #mysql IRC chat for the pointer to page sizes. I will update this answer when I find out more about the InnoDB page format and its limitations.


UPDATE
The quote above applies to the total index key length for a row, whereas my original question was about the index key length for a single-column index. My guess at this point is that the 767-byte limitation is legacy from the time when all pages were 4KB in size, and thus both single-column and multi-column indexes were limited to a total length of 767 (+1?) bytes.
I will update this question again when I have more information about:


how the page size influences the index key length,
why there is a 1-byte difference in maximum key length between single-column indexes and multi-column indexes, and
why the legacy value of 767 bytes (if it is indeed a legacy value) was kept for single-column index key lengths.