Если вам провайдер отдаёт интернет через прокси, и больше никаких вариантов -- то забудьте про любые другие схемы раздачи интернета пользователям в локалке. Убрать запрос аутентификации можно -- поставьте прокси на своей стороне, настройте его каскадом для провайдерского прокси и сделайте аутентификацию по NTLM. Тогда пользователи будут логиниться на ваш прокси с помощью тех кредсов, с которыми они в систему зашли. Например, вот методичка:
wiki.525.su/doku.php?id=squid_ad Каскадов прокси там нет, но есть про настройку в связке с AD. А каскады особой проблемой не являются.