It seems that starting with Android 5.0 we can not use "Deploy local Qt libraries..." anymore because the linker refuses to load .so files from temp folder.
I reported the issue to Google https://code.google.com/p/android/issues/detail?id=79480 and if they will not fix it, then we need to print a warning when the user selects that deploying method and to make "Bundle Qt libs" the default one.