Installing Signal without using Google Play, Still requests update of Google Play
This behavior is caused if Google Play is still active in the background.

Appearently Signal finds the service, tries to use it and finds that it is outdated. I had to deactivate Google Play via

"Einstellungen" > "Allgemein" > "Anwendungen" > "Alle" > "Google Play-Dienste" > "Deaktivieren"

rough translate

"Settings" > "General" > "Applications" > "All" > "Google Play-Services" > "Deactivate"

After that Signal gave me a notification warning me that using it without Google Play will cause increased power consumption and I could proceed with the registration.