[gothenburg]

There you go:

https://github.com/microg/android_packages_apps_GmsCore

An open-source replacement of Google services. You can use Signal with this.

[haffenloher]

I wrote a little guide on how to set it up: http://o9i.de/2015/10/23/howto-gmscore.html

Has been working reasonably well for ~10 days now. Note that I'm on Android 4.2, so I might have missed something with regard to newer Android versions.