WCF Rest Webservice with stream

You mention WSDL, which leads me to believe you're getting the error while trying to browse the metadata endpoint for the service. So, first off, WSDL and REST don't go together, so you shouldn't expect to use it at all for a REST interface. Forget the service metadata concept even exists in the REST world.

Next While it's true the REST's webHttpBinding supports parameters in front of the Stream body parameter, other bindings do not and there must either be a single Stream parameter or a message contract with headers and a stream body.

So, in the end, the problem is not with the REST webHttpBinding at all, I bet it works just fine. If it doesn't I would be absolutely shocked because you're not doing anything that shouldn't work in that department. The problem is that you're expecting the metadata endpoint to generate WSDL for the service contract you've defined and that's just not supported.