There is no really good solution to this without changing the core foundation of how libraries work. Perhaps if libraries had the ability to identify what functionality was present in them with no other information to the main binary this could be solved much more easily.
Think about it- we could throw away other package management solutions entirely. The application binary would tell the "lib fetcher" what library functions it needed, and the libraries themselves would report this information to the repository or "lib server". Rather than downloading packages of libraries, you'd download individual libraries or source tarballs which provided them and compile those on the fly.