Can I safely remove a broken recovery partition?
Answer my own question since it was straightforward.

Did this

$ diskutil eraseVolume HFS+ Blank /dev/disk0s3


Now disk utility says

Partitionstabelle für „ST4000DX001-1CE168 Media“ überprüfen
Voraussetzungen überprüfen
Die Partitionsliste überprüfen
Nach einer EFI-Systempartition suchen
Die Größe der EFI-Systempartition überprüfen
Das Dateisystem der EFI-Systempartition überprüfen
Alle Loader-Speicherplätze von HFS-Datenpartitionen überprüfen
Das Volume „iMac HD“ auf „disk0s2“ hat 0 Byte nachfolgenden Loader-Speicherplatz und benötigt 134217728 Byte.
Bei der Partitionstabelle sind Probleme aufgetreten, die den Startvorgang möglicherweise verhindern.
Fehler: Die Partitionstabelle muss repariert werden, da eine Datenpartition Speicherplatz für den Loader benötigt.


So I repaired the whole disk with disk utility which fixed the missing space for the loader. 

I am now going to create a new recovery partition.