Does a web service that is defined by a WSDL; when implemented; need to use the SOAP specification to structure the request and response messages? Can it use an alternative to SOAP? Are there any alternatives to SOAP that are being used? Vice versa: Do web services that are implemented using SOAP, need to be defined using WSDL? Bonus question: Can a REST web service be defined by a WSDL? 
Do WSDL based web services need to use SOAP?
web services
SOAP can be used without WSDL, but such services will not be found using the discovery mechanics offered by WSDL. WSDL could be used to describe any form of XML exchange between two nodes. So other formats of XML can be used.REST services can be described using WSDL version 2.0. An example of how to desribe REST services in WSDL 2.0 can be found here.See also this question on StackOverflow.