There is a Android application Threema for communication encryption and that says it does not collect user data, but it requires the following permissions: identity, contacts and device ID.
Can this application be considered really secure?
Android Permissions are a tricky subject - there are a range of reasons why an App might require some fishy sounding permission to private data:
track phone callswhich sounds like someone is listening to your private conversations, but is actually needed to pause a music player when you receive a call (This varies with many android versions)
What to do?
Best Case: You should only use apps where you trust the Publisher. And you could use a System like CyanogenMod which has integrated control - so you can decide to block any app from accessing your contacts, or decide to show a confirmation dialog each time it wants to access certain private data.
The preview for Android M also sounds like a fine grained permission control might be a standard-feature in upcoming releases...
No, such features under mobile OSs today, do not unambiguously separate between 'privacy-leaks' and 'basic needs' — and that operating system developers are partly to blame.
Details on this have been provided by other answerers, but this awareness was even reinforced in the question text.