Александр Беленченко родился 10 (или 11) июля 1827 года в семье генерал-майора, георгиевского кавалера «за выслугу» Ивана Лаврентьевича Беленченко (1792—1868). Получив военное воспитание, молодой Александр был произведен в офицеры и направлен в Конную артиллерию (1845). Оттуда он в скором времени поступил в Академию Генерального штаба, которую окончил в 1849 году.После этого Беленченко был зачислен в Генеральный штаб, а затем был назначен старшим адъютантом при штабе отдельного корпуса внутренней стражи (здесь прошла большая часть его службы). Был назначен на пост главного инспектора по пересылке арестантов.
В 1867 году Александр Иванович был произведен в генерал-майоры, а в 1879 году — в генерал-лейтенанты.
В том же году, после создания Главного тюремного управления МВД, должность главного инспектора по пересылке арестантов стала промежуточным звеном между военным ведомством и Министерством внутренних дел, которое настаивало на упразднение этой должности и передаче её функций в МВД. Беленченко пытался отстоять свою должность, но без особого успеха.
В этот период А. Ф. Кони описывает Александра Беленченко как «звероподобного начальника пересыльной части» , «грязного циника» , «маскарадного героя» и «почетного члена домов терпимости» , заявлявшего, что в России и Сибири административно пересылаются ежегодно от восьми до десяти тысяч человек..mw-parser-output .ts-Начало_цитаты-quote{float: none;padding: 0.25em 1em;border: thin solid #eaecf0}.mw-parser-output .ts-Начало_цитаты-source{margin: 1em 0 0 5%;font-size: 105%}.mw-parser-output .ts-Начало_цитаты-quote .ts-oq{margin: 0 -1em -0.25em}.mw-parser-output .ts-Начало_цитаты-quote .ts-oq .NavFrame{padding: 0}.mw-parser-output .ts-Начало_цитаты-quote .ts-oq .NavHead,.mw-parser-output .ts-Начало_цитаты-quote .ts-oq .NavContent{padding-left: 1.052632em;padding-right: 1.052632em}Да помилуйте, ваше сиятельство, зачем мне смотреть причины [ареста и ссылки]! Не смотрел и смотреть не намерен! Зачем мне их знать Ко мне приводят человека и говорят: «В Якутск!» — «Слушаю-с!» — Кладу его в колесо, повернул, — и он сделал быстрое круговое движение рукою, — трах! Он в Якутске. А кто он, зачем и почему — мне-то какое дело Я, ваше сиятельство, — машина; повернул колесо: раз, раз — и готово; раз, раз — и готово! А до личности мне и дела нет! С какой радости!.mw-parser-output .ts-Конец_цитаты-source{margin: 0.357143em 2em 0 0;text-align: right}— слова Беленченко, передаваемые А. Ф. Кони.
С 1880 года, выйдя в отставку, Беленченко состоял членом Главного военно-тюремного комитета (1864—1884), руководимого генерал-адъютантом Иваном Лутковским, и в этом звании оставался до своей кончины.24 февраля (или 24 апреля) 1884 года Александр Иванович Беленченко умер в Санкт-Петербурге и был погребен в Александро-Невской Лавре.