Ну для начала выкинуть те библиотеки, которые IDE по умолчанию включает в проект, в Eclipse это support v4, в Android Studio аж v7 но она обеспечивает AppCompat, то есть Material design на Pre-Lollipop (ниже 5.0), стоит ли им жертвовать.
Нескольких мегабайт уже не будет, дальше не смотрел, т.к. нет необходимости, если у вас она есть и вы видите еще более маленькое приложение то apktool в руки, а барабан на шею!