Какие базовые знания нужно знать, чтоб начать изучать программирование?

Отвечу как человек, который тоже решил изучать программирование. Советую скачать книгу Столярова "Азы программирования. Том 1". Автор выложил книгу в свободный доступ, и ее можно скачать на сайте: http://stolyarov.info/node/187. Настоятельно рекомендую также обратить внимания на предисловия к книге (вообще советую прочитать их всем,кто заинтересован в проекте), т.к. там дано подробное описание плана обучения. Столяров убежден, что программирование нужно начинать изучать в ОС UNIX. Также там объясняется, почему выбор пал именно на язык Паскаль (уже предчувствую критику в сторону автора). Помимо этого, там кратко описана история ЭВМ, работа компьютера, история UNIX, даны основы дискретной математики, теории алгоритмов, двоичной арифметики и т.д. Это как раз таки те базовые знания, которые вы имели в виду. Даже если вас тошнит от Паскаля и вы не планируете его изучать, то прочитайте хотя бы 1 часть книги , где даны предварительные сведения о программировании. В общем, мне кажется, эта книга подойдет как раз для начинающего программиста. Также хотел бы прочитать мнения опытных программистов обо всем вышесказанном.  

Информация о самом авторе: 

Андрей Викторович Столяров (род. 25 декабря 1974 года) — кандидат физико-математических наук (2002 г., специальность 05.13.11), доцент (2009 г.), кандидат философских наук (2012 г., специальность 09.00.11), работает на кафедре алгоритмических языков ф-та ВМК МГУ им. М.В.Ломоносова с 2002 г. в должности ассистента, с 2010 г. в должности доцента. 

P.S. Кстати, насчет английского. Английский просто MUST HAVE. Если планируете связать жизнь с программированием или заняться им в качестве хобби - идите и учите английский. Самый новый и качественный материал пишут на нем.