This would use the “proper” lifetime in the closure and should allow returning a reference back. The trouble now, of course, is the borrow resulting from calling the closure does not allow mutating the slice.
The readonly methods, such as binary_search_by_key, do use a signature like above, probably for this very reason (to allow returning references tied to the closure arg).
So in fact, I don’t think region inference has anything to do with this; there’s just no way to express the lifetime relationships here accordingly.
It can remain FnMut if you also bind the parameter mutably, like mut f: F. That mut makes no difference in the API to the caller, as they just provide f by value, but you need it mutable to call FnMut. You didn't need that for the plain by_key version because there you're just passing that by value as a parameter again.
There are already 6 sorting methods -- 3 variants of sort and 3 sort_unstable -- so I fear that adding ref versions of each might be too much. But I found a related issue for this, so maybe you could propose it there first: