Для начала надо определить что есть основы программирования:
Во первых я бы сказал это логическое мышление в целом, понимание алгоритмов (как минимум что это означает), написание алгоритма вещь вообще полезная для чего либо кроме Hello World!.
Во вторых это знание определений что такое переменная, массив, циклы итп. Все это плюс-минус едино для всех языков программирования.
В третьих - основные алгоритмы и приёмы, опять же универсальные для всех языков. Ну например ... как перебрать массив, обрезать строку или вычленить слово. Опять же используется вне зависимости языка и задач.
Вернемся же теперь к вашему вопросу - писать что-то под Android можно наверное и без основ. Просто копируешь чужой код, правишь что-нибудь, собираешь так сказать "Lego". Если вам нравится - вперед, но от основ это как раз очень далеко. И да изучать сходу язык с ООП ИМХО не есть здравая идея. Либо это займет кучу времени, либо вы будете собирать примитивные Hello World'ы.
Если же хотите начать с основ, возьмите язык попроще и не заостренный на ООП. Лично я когда-то в школе начинал с QBASIC - отличная вещь для начала, но ... Устарел, причем давно. Из современного я бы посоветовал JS, он же EcmaScript. Для него есть хорошие скринкасты того-же Sorax'a, да и используется много где. Но это не на андроид (хотя я лукавлю, можно писать на JS с помощью Cordova, но это далеко не начальный уровень).
