1) Договориться с правообладателями музыкальных композиций --- это правильный ответ в комменте
2) "Вконтакте многие выкладывают музыку и все её слушают, проблем похоже не возникает. "
А это работает по причине:
На каком этапе могут возникнуть проблемы с правообладателями? Еще на момент публикации приложения в playmarket/applestore с первым контентом или уже позже, при работе приложения конкретно по каждому треку?
проверки треков уже после публикации