Определенно можно играть в H263 на этом устройстве с вашими требованиями. Но вам нужно оптимизировать декодер или купить его;)
Еще один кодек, имеющий быстрый декодер, это On2 VP8. Но является собственностью и не доступен бесплатно. Кроме того, я не знаю, это быстрый декодер или это просто маркетинг.
Также вы можете посмотреть на некоторые редкие кодеки, такие как Theora / Dirac . Или кодеки в FFmpeg (libavcodec). Последний оптимизирован для деталей ARM (иногда до ARMv7 с NEON). Может быть, вы можете найти что-то, если качество не очень важно. Например. Н.261:)
Но я думаю, что лучший выбор - оптимизированный H263.
Кстати: какой процессор / архитектуру ARM вы используете?