In my program, it gets MP4 video in, and I want it to output a MP3 (without any server-side stuff.) Since Android (and my app) needs to run on many different hardware configurations, this means I probably cannot use FFMPEG. I know this may be very battery and processing power intensive, especially for a mobile phone, but I need this option for my users. I cannot find any native libraries for Java that don't use FFMPEG.
I see little problem with FFMPEG, since apparently it runs on 11 architectures supported by Debian. Only architecture not supported is apparently m68k, others are old versions in ports to FreeBSD kernel, or Hurd kernel. And from what I know of Android, fact that it's based on ARM isn't going to change any time soon.
Of course, there could be some issues with Java wrappers around native code. Is that the issue? I'm not an Android nor a Java programmer, but I'm sure you can detect the platform and dynamically load appropriate native wrapper.