I have found a way how to force this unfriendly tablet to play the video in Adobe Air app by encoding it into FLV format and then embedding it into a swf via Flash pro. In this case I had to sync the app and video framerate(24fps). I have also set usingVideo flag to false in app descriptor. Playback quality and performance are not very good but it's the only working method at the moment - I guess those can be improved by tweaking flv encoder params.
Update 4/3/2014
As the video playback embedded into swf was awful on the target device I have decided to download all the android versions of air runtimes starting from 3.1 and test normal video playback on these. Finally I have got the following results:
3.1.0.557 - NO
3.2 - YES
3.3.0.365 - YES
3.4.0.254 - NO
3.5.0.60 - NO
3.6.0.609 - NO
3.7.0.186 - NO
3.8.0.147 - NO
3.9.0.141 - NO
4.0 - NO
In the end I have found the solution - I have uninstalled all modern versions downloaded from google play and installed 3.3.0.365. I think my experience can be useful for those who develop AIR apps for android where target devices are noname low-end android tablets.
PS. I found another possibility to make video playing by using an swf embedded into an html page and displayed by StageWebView but this method has so much obstacles(FP security rules, ExternallInterface barriers) so it has no sense to implement it.