Testing video encoding with the MediaCodec API in several devices, I noticed all of them have encoders for h264, h263, and MPEG-4.
Are any of these guaranteed to be supported by all devices which have at least Jelly Bean, even if the actual encoding done by MediaCodec is done by software instead of hardware?
The Android Compatibility Definition Document (CDD) defines a set of mandatory features. Google "Android <version> CDD" to find the appropriate one.
For example, if you open the 4.3 CDD, and flip down to section 5.1 ("Media Codecs"), you can find a table of codecs. Section 5.2 ("Video Encoding") has some additional details.