If you look closely at the Google compatibility matrix, you will see that MP4 / H264 encoding support began with the release of Android 3.0. MP4 / H.264 playback was supported by all Android devices on Android 1.0, so you do not need to limit the availability of new versions of Android (unless you have other API compatibility requirements).
Through VideoView, video playback on all these devices is performed using the hardware decoder provided by the phone chipset. To ensure compatibility, the video must be encoded to the lowest denominator. Google provides "Video Encoding Recommendations" at the bottom of the page that you linked; I also wrote an answer describing how we transcoded to the MP4 / H264 form, which plays on all Android devices.
Not knowing what Vine does with their videos, perhaps the video is not all encoded using the unified encoder settings. They can shoot videos directly from phones and transfer them without additional processing on the server side to ensure wide compatibility; I dont know. In this case, it may seem difficult for you to develop an Android application that can display content without: a) implementing your own software codec (for example, such as RockPlayer, MX Player or VLC) or b) transcoding the video on the server (which is likely to run into Vine terms of service).