Relatively simple actually, without copyright. Download Spotify, rename app to Spudify, re-upload to app store. Done, easy peasy. Hardest part about it would be decompiling the existing app, which is definitely possible and may not even be necessary.
The real truth is, however, that in this hypothetical world there would be no Spotify to copy and there would be much, much less music available to stream on Spudify.