You don't have to use a streaming service. Just buy MP3s, or buy CDs and rip to MP3/Ogg with an open-source ripper, and store the files on your computer and phone. Android has a built-in music player that plays Oggs just fine; no network connection needed.
