Очень быстро, я за две недели выучил и накидал 2D-игру на Android правда на Canvas. Всё простенько, различные активности, обработка событий от тача, тракболла и т. д. Самое главное писать наиболее эффективные алгоритмы чтобы тормозов не ощущать, особенно со строками поосторожнее быть имея виду на счёт производительности, конечно если есть из начальные знания, то бишь я ещё начинал на Java SE, EE, ME. Главное в Android собственная склёпанная виртуалка не родная байт-коду Sun-овской.
Знать C++ можно по-разному.
Если вы умеете писать на С++ консольные хелловорлды, то в случае с Android вам это не поможет ничем. Консольные приложения на Android вообще не приняты.
А за сколько - это зависит от вас и от того, чему хотите научиться.
Linux не нужен. Можно писать и под Windows.
если неплохо знаете С++, то вас может заинтересовать это
http://habrahabr.ru/post/203014/
хотя, конечно, если вы собираетесь писать приложения, а не игры, то лучше, конечно, изучить Java.
я простое приложение за пару ночей ненапрягаясь написал