К сожалению, вам нужно изменить код прокси. Другие возможности, о которых вы упомянули, не будут работать - класс parial не будет перезаписывать существующую функциональность, и я не знаю, как заставить интерфейс выполнять то, что вам нужно (усугубляется тем, что нет возможности даже прокси-генератор знает, что вы намереваетесь реализовать интерфейс).
То, что я делал в прошлом, в ситуации, когда у вас есть доступ к источнику веб-сервиса, - это написание небольшого приложения, которое будет анализировать код (как текст) в файле .asmx.cs веб-сервис для извлечения имен всех методов, которые помечены [WebMethod]. Затем приложение «исправляет» файл References.cs, вставляя соответствующие атрибуты в прокси-методы на основе некоторого файла настроек или чего-то подобного. Это хорошо работает, потому что соглашения об именах в прокси очень точно соответствуют именам методов в исходном сервисе.