Threema

• fee can be paid with Bitcoin
• no phone number required
• android client is open source and can be installed directly from Github or F-droid
• push notification works without google playstore