Ну тут есть много вариантов, первое что приходит в голову:
Яндекс.Музыка
На данный момент имеет уже довольно большую музыкальную базу. Есть функция загрузки треков для прослушивания без инета. Можно юзать как через браузер, так и через приложуху.
Главный недостаток у Яндекс.Музыки — пробный период, ограниченный 30 днями. По истечении этого срока приложением можно будет пользоваться только после оформления подписки (169 рублей/месяц).
Ещё можно попробовать SoundCloud, если ещё не.
Хороший сервис, также можно юзать и с браузера или приложения. Полностью бесплатен. Главными его плюхами считаю то, что он очень популярен на просторах нашей необъятной, что означает большое количество отечественного и актуального контента. И помимо музыки, можно найти подкасты и даже лекции.
Ещё слышал про приложения Zvooq, Guvera Music, Musicbox, Music D/L, но за них ничего рассказать не могу, так как не пользовался.
Конкретно в ВК — никак. Все приложения, которые предлагают эту функцию, или врут или используют кэш. Кстати, в мобильной версии есть сохраненная музыка. Там можно слушать оффлайн. Однако, это все тот же кэш.
Вот почему надо переходить на SoundHost там с музыкой все норм.
SoundHost – это онлайн-платформа (мобильная и веб), которая позволяет слушать любимую музыку онлайн, следить за творчеством артистов и за музыкальными событиями.
Прекрасно работает @vkmusicbot в телеграме. К управлению надо привыкнуть, но музыка сохраняется в кэше телеграма и есть возможность прослушивать её оффлайн (как в приложении vk до изменений).
Лично я знаю лишь одно приложение с обходом запрета ВК на музыку - VK Coffee. Там стоит функция обхода блокировки, поэтому можно искать музыку, слушать без ограничений.