Jolla - The First One is the way to go! Actually, it's a little rough around the edges but the community is so active and the software updates so frequent... it will be another product in a few months
I'll probably go with Moto X - a little bit of customization goes a long way for my purchase and the recent drop in price for an unlocked phone also helps - but I'm US based, Jolla isn't an option at the moment. Android and security - almost a bit laughable out of the box. You've done your research it seems. Jolla is invariably more secure though. But be careful, Knox has known security vulnerabilities... (38)
Threema uses Google Cloud Messaging (GCM) to notify the app of new messages in the background. If Google Apps are not installed, you will not be informed of new messages unless you enable polling in the app (the polling interval is fixed at 15 minutes and will cause some additional battery drain and data usage)