So this is a really tough problem, and I don't believe there are any APIs out there to achieve what you want.
What you can't do: Custom Permissions
While they sound like a good idea custom permissions are defined in the AndroidManifest.xml. Checkout this SO answer on how to define/use them, but they look something like this:
<permission
android:name="com.testpackage.mypermission"
android:label="my_permission"
android:protectionLevel="dangerous">
</permission>
To use the permission all another application has to do is put the following in their own AndroidManifest.xml:
<uses-permission android:name="com.testpackage.mypermission"/>
Since Android APKs are trivial to reverse engineer to gain the most basic information about an application; this would fall your fear of someone gaining access to the APK. Anyone with a rooted phone can pull the APK from their phone.
I do admit that there is likely more to using a custom permission than just that XML line. But it seems if someone is going through the trouble to begin with, then they can figure it out.
Solution?
This is a tough problem, because at some point you'll need to ask the user to verify that they trust an application to be used with your core app. If the user verifies that they trust the app then I would probably record the application's signature; which can be found at runtime. If the signature changes from what you have recorded then it's not the application the user trusted.
This is probably the easiest solution. Verifying the signature itself should be possible as the META-INF/CERT.RSA contains the signature and public key to verify the signature. I believe this post on SO shows how this can be done.
Again, you're still relying on the user to verify trust of an application through your core application. I'm not sure if this is acceptable to you or not.
