Каким образом Бог меняет совесть нашу на другую, благую совесть? И всегда ли это происходит при крещении? (См. стих)

Нет. Это всего лишь кулич (заманилово и зазывалово) , которым размахивают перед носом крещаемого )))
Все вещи в труде! Бдите!

Если человек искренне хочет измениться в лучшую сторону, то Бог ему в этом помогает, через частичку Святого Духа, которую мы именуем совестью.
При этом сама совесть не меняется, но, с Божьей помощью, меняется наша чувствительность к её "голосу".

Простите, это была ошибка.

Бог нам помогает, а меняемся мы сами.

...Неужели не знаете, что все мы, крестившиеся во Христа Иисуса, в смерть Его крестились?
Итак мы погреблись с Ним крещением в смерть, дабы, как Христос воскрес из мертвых славою Отца, так и нам ходить в обновленной жизни.
(Рим. 6:3,4)

... Но те, которые Христовы, распяли плоть со страстями и похотями.
(Гал. 5:24)

...Но вы не по плоти живете, а по духу, если только Дух Божий живет в вас. Если же кто Духа Христова не имеет, тот [и] не Его.
А если Христос в вас, то тело мертво для греха, но дух жив для праведности.
(Рим. 8:9,10)

К сожалению великому не все крещаемые подходят к осуществлению этого шага со всей ответственностью. В итоге все их слова обетования служить Богу доброй совестью остаются только словами. Внутри их не произошло обновления, человек ветхий днями не оставил их и они остались рабами греха, греха к смерти.

Почему Иисус требовал, чтобы его ученики подвергались крещению? Дело в том, что это – подходящий символ их беззаветного посвящения Богу. По всей земле необходимо было проповедовать «Евангелие» , и производить из «людей всех наций» учеников (Матфея 24:14; 28:19). Это означало, что Бог больше не имел дело исключительно с еврейским народом, состоящим из людей, которые посвящались ему с рождения. Корнилий и его семья были первыми язычниками, или неевреями, принявшими истину об Иисусе Христе и подвергнувшимися крещению.
То, что принимающих крещение погружали в воду, показывало, что они умерли для жизни, вращающейся вокруг самих себя. Поднятие их из воды символизировало, что теперь они живы, чтобы творить Божью волю и ставить ее на первое место в своей жизни, как делал Иисус (Матфея 16:24). Принятие крещения «во имя Отца и Сына и Святого Духа» указывало на то, что принимающие крещение познали и приняли истину об Отце, Сыне и святом духе, и осознали, чтоL9; они (Отец, Сын и святой дух) собой представляют (Матфея 28:19; сравни Деяния 13:48). Акт крещения был просто исходным шагом к послушанию Богу и подчинению его воле.