It is definitely possible to play the H263 on this device with your requirements. But you need to optimize the decoder or buy it;)
Another codec that positions itself as having a fast decoder is On2 VP8. But it is proprietary and inaccessible for free. Also, I don't know if this decoder is fast, or is it just marketing.
You can also watch some rare codecs such as Theora / Dirac . Or codecs in FFmpeg (libavcodec). The latter is optimized for ARM (sometimes up to ARMv7 with NEON). Maybe you can find something if quality is not very important. For example. H.261 :)
, H263.
BTW: ARM-/ ?