@robotamadeus,
Not without permission. Who you owe rights (royalties) to depends on if it was released by a record label who retains rights to the song or by an independent label where the band/songwriter retains the rights.
That doesn't mean you can't make a profit off of your cover, but you need to share that profit with those who own the rights to the song.