Wenn Du es coverst, also 1:1 nachspielst brauchst Du keine Verlagsfreigabe, denn der Komponist hat es Rio Reiser auch erlaubt (auch wenn er selber Komponist war), dann muss er es Dir auch erlauben.
Wenn Du es aber bearbeitest, sprich veränderst, musst Du die Erlaubnis des Rechteinhabers sein. Wenn Du Dir sicher sein willst, hole sie Dir ein.
Ein paar [g=45]bpm[/g] anderes Tempo ist für manche schon eine Bearbeitung!