One could procure the necessary rights from the copyright owners / artists for all the training data. Sure, it would be quite costly and take a long time - but it is possible.
No, it isn't possible. Tracing copyrights for many things is literally impossible. Might be owned by defunct company X that died out several decades ago and had records destroyed in a fire.
One does not need every single copyrighted object in the world, just a large, diverse and representative set. One would have to skip the cases where rights cannot be secured. This is possible, see for example Spotify.
