Firebase TypeInitializationException/DLLNotFoundException on Android

Hi! I am trying to use Firebase within Unity (5.5.2). It works fine in the editor, but when I make an Android build and try to run it, I get the following error:

There is only one line of code that I am trying to run:

FirebaseApp.DefaultInstance.SetEditorDatabaseUrl(myurl);

What I did

I created a new project, set it to Android, imported the Firebase SDK from this site: https://firebase.google.com/docs/unity/setup and importet the FirebaseDatabase.unitypackage. Then I created a script that tries to set the URL, which works fine in the editor (I can even go further and read and write to the database).

Fixes I tried

• setting the PATH variable according to https://github.com/firebase/Firebase-Unity/issues/2

• updating everything in my SDK Manager, all the Google stuff and Android tools, SDK for each version

• uninstalling and reinstalling Java (64 Bit)

The very strange thing is, that the same project works for another person. When he builds, I can run the app on my phone just fine. So the issue must be something in my workspace. Here is what I got:

• Windows 8.1 and 7 (64 Bit)

• Unity 5.5.2f1 (also tried 5.5.0)

• jdk-8u121

• android-ndk-r10e

• Go Play services v39

• Google Repository v44

Can anyone think of ANYTHING at all that might cause this issue? There must be something I am missing...

EDIT I also tried to run the quickstart database project (https://github.com/firebase/quickstart-unity/tree/master/database/testapp), which also works fine in the editor, but in a build results in this message:

"One or more Firebase dependencies are not present. Current dependency status: UnavailableOther"

Which I assume is the same error, just masked by exception handling.