The problem is solved now, but the reason for the error was quite unexpected, all the usual suspects for such errors were eliminated on start, and I have learned something new. See my answer below.
W/System.err: Caused by: java.lang.UnsatisfiedLinkError: Couldn't load cld from loader dalvik.system.PathClassLoader[dexPath=/data/app/com.hyperionics.avar-2.apk,libraryPath=/data/app-lib/com.hyperionics.avar-2]: findLibrary returned null
Caused by: java.lang.UnsatisfiedLinkError: Native method not found: com.hyperionics.avar.CldWrapper.detectLangNative:(Ljava/lang/String;)[Ljava/lang/String;
There was no satisfactory answer during the bounty period. I ordered the device and will have to debug what most likely is a system bug in the device ROM for Android 4.2.2 update...
It turns out that sometimes, when updating an app from Google Play, native libraries are not installed correctly. Maybe the installer runs out of space, or some other strange system bug kicks in. Please see also this SO question and answers.
My HTC One ordered from Google Play arrived, and... mystery solved! The same crash happened also on the original Android 4.2.2 from Google Play. The problem was my library name: cld, which produces a shared library named libcld.so. Apparently the system has another shared library with the same name, where the methods I expect are not present, of course... Probably some "plugin" loaded this other libcld.so into the process memory, and my own library was skipped. I renamed the native library and the program started working at once.
I was not aware of the possibility of such name clashes on different builds of Android... Did anyone reading this see a warning somewhere in NDK docs about it? I guess I'll prefix from now on all native libraries I create with my company name or something.