I think the most practical solution to this, requiring only a change in practice and not in standard, would be for link shorteners to start doing HEAD requests

I think the most practical solution to this, requiring only a change in practice and not in standard, would be for link shorteners to start doing HEAD requests on the urls they shorten and unwrap it to make their shortened link canonically correct if it results in a permanent redirect. Yeah, there are things that might have some problems with this, but they're things that are probably somewhat abusive to the 301 status code to begin with.