This paper presents a flexible service deployment architecture for the automated, on-demand deployment of distributed services in programmable networks. The novelty of our approach is (a) the customization of the deployment protocol by utilizing modular building blocks, namely navigation patterns, aggregation patterns, and capability functions, and (b) the definition of a corresponding service descriptor. A customizable deployment protocol has several important advantages: It supports a multitude of services, and it allows for an ad hoc optimization of the protocol according to the specific needs of a service and the current network conditions. Moreover, our architecture provides an environment for studying new patterns which aim at reducing deployment latency and bandwidth for certain services. We demonstrate how the developed architecture can be used to setup a virtual private network, and we present measurements conducted with our prototype in the PlanetLab test network. Furthermore, a comparison of a distributed pattern with a centralized pattern illustrates the performance trade-off for different deployment strategies.