Оцениваешь время. С опытом твоя оценка все точнее. Умножаешь на 3. Обязательно. Это еще в прошлом веке объяснил проджект-менеджер, делавший операционную систему. Почитай, книжкам маленькая. Не пожалеешь. Брукс "Мифический человеко-месяц".
При этом типичный российский заказчик подобных работ хочет точно знать бюджет
Ты как заказчик, поступал бы также. Это свойство всех заказчиков. Хоть канадцев, хоть французов. Не проблема. И вообще заказчик не должен внимать в такие детали, не царское это дело. Не озвучивай твои затраты на чисто работу. Включай туда все накладные расходы. Не забывай оценку завышать. В 3 раза. Фактически это не обман. Любая оценка все равно слишком оптимистична. И завышение в 3 раза превращает ее в нормальную. Читай по этому поводу книжку Брукса.
ничего слышать не хочет про оплату за фактически потраченное время аргументируя это формулировками вроде «вот ты решишь проблему и скажешь мне -давай 100500килоденег».
Существуют различные виды организации работ и оплаты. Те, с кем я работаю давно, уже знакомы с моими расценками и не боятся. Применяю с ними оплату "по факту реально выполненных работ" постоянно. Заранее согласовываем только самые большие суммы. Ну а если заказчик хочет жесткого бюджета, то обязательно
ограничивай его в объемах работ. Это можно сделать просто: система не будет уметь 1), 2), 3) таких-то вещей. Или детально прописывай, что значит "работа завершена".