Is there any other way to consume a SharePoint 2013 web service other than adding its service reference in visual studio?
What if I want to do this at runtime? Is there an example available?
Yes, you can do this using posting SOAP messages to the web service using
HttpClient object (MSDN for HttpClient). You can look here in the answer https://stackoverflow.com/questions/14336414/httpclient-soap-c. It shows how to make a SOAP web service call using C#.