Not sure if listening skill to tones in Chinese songs has its own implication, I get the impression that songs are generally harder than daily conversations for a non-native language.
To answer the first part of your question: native speaker can not tell the lyrics all the time. One particularly interesting case is the songs by Jay Chou, who is one of the most famous Chinese singers since 2000. As a native speaker, I can only get about 10%-30% of the lyrics by only listening to his rap songs.
However, tones seem not to be problem, rather, it is the speed that makes the difficulty for native speakers. Personally, I do not really find tones as the problem. Perhaps only when listen to special dialects, nonstandard tones may be problematic.
To improve, the suggestion could be similar as what you thought. Start with easier ones and try to understand in the context. This process should be very similar to or same as general listening skill.