That's not the case anymore. Spotify now lets you change the profile pic without logging into Facebook. Just access your profile from the desktop app and you should see the word "Change" on your blank profile pic or the pic that is existed on there.
For the people having trouble, you need to actually download the computer version of spotify (it's similar to how itunes has a limited web version and a full computer version). You should find it on the home page of spotify. It's not available on the web player.
At the moment, I believe the only way to change it is through the Desktop app.
Hope it helps. :)