Where should one start to first learn how to solo over changes if it was just any song? Is there book that teaches you about learning about pentatonic scales, modes, relative major and relative minor?
You can learn all of the scales in the world, but if you don't know the chord progression you will never learn to play over any changes.
Again, if you want to learn to play over the changes, learn the changes (the chords) first. You can not skip this step and expect to understand anything beyond it.