I need to know more about your interaction with the web service. For example, if you need to call it and bring back some data then you'll need to write a C++ or C# custom action. If you only need to publish some data to the service on a best effort basis with no return data flow then you could get away with writing an EXE and just calling that from the install.
Also be sure to consider what should happen if your server isn't available. Does this block the install or is it ok?
If you choose to write a C# custom action, be sure to google for "DTF - Deployment Tools Foundation". You'll find plenty of articles and tips about it on my blog. Basically you create a class that consumes your WCF and exposes a client side private API for it then you write a custom action class that interacts with Windows Installer and passes data back and forth to your first class.