"Постесняюсь спросить" (образованное от "стесняюсь спросить") устойчивое выражение, по факту действительно употребляемое на равне с "не постесняюсь спросить" и зачастую эти два выражения взаимозаменяемы. Но я бы не торопился делать вывод, что первое получилось усечением второго, скорее это "не постесняюсь спросить" логическое развитее изначального "стесняюсь спросить", образованное по типу "да не убоюсь" - да не постесняюсь я спросить :).
Подразумевается, что человек робеет, но всё-таки осмеливается и задаёт вопрос. В большинстве случае фраза несёт иронический оттенок, как в "стесняюсь спросить, куда это ты намылился, не сделав домашнюю работу". Спорить со словоупотреблением и говорить, что если стесняется, то чего ж спрашивает - так же продуктивно, как спорить, почему говорят "таблетки от головы", когда ясное же дело, что не от головы.
Я тот ещё авторитетный источник, но лично мне известно очень мало случаев использования обоих этих словосочетаний в досоветской периодике и литературе - буквально по пальцам руки пересчитать. Но даже если я ошибаюсь, и даже если так говорили и в XIX веке, то всё равно берусь утверждать, что пик словоупотребления пришёлся на советское и постсоветское время.
"Стесняясь спросить" - так никто от первого лица не говорит.
Ну и что касается считать ли эту фразу словом-паразитом. Тут надо дать строгое определение того, что считается словом-паразитом. Ввиду отсутствия такого определения у вас, дам своё, созвучное данному в википедии: слова-паразиты - это слова, употребляемые в предложении, но не несущие в данном контексте смысловой нагрузки. Их можно выкинуть из предложения без потери или изменения информационной ценности предложения.
Кстати, из той же статьи можно узнать, что, вообще говоря, это дискуссионный вопрос, действительно ли такие слова не несут никакой нагрузки и не имеют никакой функции.
В узком смысле "стесняюсь спросить" точно не слово-паразит, всё-таки ставить это словосочетания в один ряд с "это самое", "эээ" или "ммм" было бы натяжкой.
В широком - ну, давайте попробуем сравнить две фразы:
- Стесняюсь спросить, а как вы познакомились?
- А как вы познакомились?
Эквивалентны ли эти фразы? На мой взгляд нет, не эквивалентны. Но это, разумеется, вопрос метрики.
Ну и напоследок добавлю картинку - представьте, ту же картинку, но с подписью без "слов-паразитов":