Ubuntu Sverige

Finns det spotify för linux som man inte kör genom wine?

Ja, det finns det. Men det kräver att du har ett betalkonto på Spotify för att det ska fungera: http://www.spotify.com/se/download/previews/
Kolla under rubriken "Debian".