Как сказал DJ: единственный способ сделать это - написать собственный веб-сервис, который затем использует объектную модель SharePoint для создания сайта / изменения навигации.
Когда вы говорите, что вам нужно использовать веб-сервисы, означает ли это, что вы не можете не использовать dll (в решениях sharepoint)? Если это так, то единственный способ - изменить навигацию вручную после создания сайта.