Pretty sure you can't delete all subscribers on the All Subscribers list all at once. If it was another list, you can delete the List Object, which will delete all of the subscribers in it.
Here's a sample SOAP envelope.
<?xml version="1.0" encoding="UTF-8"?>
<s:Envelope xmlns:s="http://www.w3.org/2003/05/soap-envelope" xmlns:a="http://schemas.xmlsoap.org/ws/2004/08/addressing" xmlns:u="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-utility-1.0.xsd">
<s:Header>
<a:Action s:mustUnderstand="1">Delete</a:Action>
<a:MessageID>urn:uuid:cec6826f-1ac3-4559-934b-a5ad8e081c3c</a:MessageID>
<a:ReplyTo>
<a:Address>http://schemas.xmlsoap.org/ws/2004/08/addressing/role/anonymous</a:Address>
</a:ReplyTo>
<a:To s:mustUnderstand="1">https://webservice.s4.exacttarget.com/Service.asmx</a:To>
<o:Security xmlns:o="http://docs.oasis-open.org/wss/2004/01/oasis-200401-wss-wssecurity-secext-1.0.xsd" s:mustUnderstand="1">
<u:Timestamp u:Id="_0">
<u:Created>2015-01-30T15:29:13.355Z</u:Created>
<u:Expires>2015-01-30T15:34:13.355Z</u:Expires>
</u:Timestamp>
<o:UsernameToken u:Id="uuid-3bd5c867-ef2e-4768-a5e7-3a119b1a8765-11">
<o:Username><!-- Removed--></o:Username>
<o:Password><!-- Removed--></o:Password>
</o:UsernameToken>
</o:Security>
</s:Header>
<s:Body xmlns:xsd="http://www.w3.org/2001/XMLSchema" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance">
<DeleteRequest xmlns="http://exacttarget.com/wsdl/partnerAPI">
<Options>
<SaveOptions />
</Options>
<Objects xsi:type="List">
<PartnerKey xsi:nil="true" />
<ObjectID xsi:nil="true" />
<CustomerKey>aspriggs-test-list</CustomerKey>
</Objects>
</DeleteRequest>
</s:Body>
</s:Envelope>