It seems rather sad that Signal’s author doesn’t want it distributed outwith Play, but if that’s his choice, is there any similar, trusted, secure comms app that does play nicely with FPOOS?
Even installing Signal via APK copied off another Play-enabled 'phone I get the strong impression it’ll be a deeply substandard experience because of its complaints about the absence of Play and its warning about using extra battery in order to be able to receive messages…
Conversations is an XMPP messenger which supports OMEMO encryption (besides OTR and GPG). I use it for regular communication with my girlfriend and can’t complain. The only thing you have to choose carefully is the XMPP server which must meet some requirements for OMEMO to work.
In the absence of the Google Push Method signal has to poll for new messages. This will a) give you a possible delay in receiving messages, b) force signal to stay awake and poll regularly. That’s what this means… So, possible, yes. I don’t think polling regularly will make the experience too bad. But for a reasonable conversation you might have to poll manually…
Signal distribute an official APK that (I read) autoupdate itself: https://signal.org/android/apk/
As @lklaus said, it works without Gobble push messaging (part of GMS) by pulling messages on a regular basis, but on the contrary I think it’ll be enough to maintain a conversation. You just need to disable battery optimisation for Signal to avoid sync fails.
If you don’t like GMS/openGAPPS, but still want push messaging to work, you can use microG. It’s a free/libre implementation of Google cloud messaging stuff.
For downloading apk files from the play store, take a look at this guide: #installanyapp
There’s also a paragraph about microG in this guide.
Be aware that implementation is libre, but push messaging service is not. You’re still feeding Gobble with a lot of metadata, just you have better control over it.
Me and some others from the Austrian Fairphoners use Kontalk (www.kontalk.org) which is a FLOSS XMPP Messenger also available on F-Droid. It uses your phone number for registration.
Also, Kontalk has the same encryption as Signal (and WhatsApp), IIRC (the Axolotl protocol).
Furthermore, it runs over a federated network or servers (multiple owners), not a centralized network of servers (single owner), which is one of the main criticism of Signal (the other being rejecting forks on their network).
For a (huge, technical) deep view in the topic, read this FSFE’s article on privacy and encryption in mobile messengers: https://blogs.fsfe.org/h2/2016/05/31/why-privacy-is-more-than-crypto/
Not to forget the necessity to provide a phone number to identify oneself.
…which is one of the main criticisms as well for Kontalk.
With Conversations you don’t register with your phone number but instead create a normal XMPP account or use your existing one. You can communicate cross platform with any XMPP client which supports OMEMO (https://en.m.wikipedia.org/wiki/OMEMO) (successor of Axolotl), e. g. Gajim with plugins.
you may also want to give wire a chance (www.wire.com).
It is not available on f-droid (yet?), but you can download the up-to-date version from their download page.
I am also using Conversations and very happy with it 
If you don’t have an xmpp / jabber account yet you can sign up to conversations.im for one year for free, as far as I know.
Some related reading on the whole messenger situation, why xmpp is the answer, and how to get started (even with your own server if you want): https://ilu.servus.at/issue9.html
I’m also very happy with Conversations. Another option that works well to talk to iOS users (where XMPP support isn’t up to Conversations standards) is Riot which is based on the Matrix protocol. As with XMPP servers federate and it’s possible to run your own server.
I still prefer Conversations for one-to-one chat between Android phones. Riot on the other side is my goto app for group chat and conversations with iOS users.
I personally use Threema. Its paid, but a great Messenger. However you would still have to use polling, since it too uses GMS normally.
This version is true, works without gapps and autoupdate without any other issues that on Android 6 you have to disable the battery optimizations, so you stay as in android 5.1. Anyway Telegram-FOSS or Whatsapp work without gapps the same way.
I’m closing this topic as the “is it possible to use Signal on FPOOS” part is answered and the “which messenger do you use/recommend” part is best discussed here: