USB-PD only uses two wires (GND and VBUS), but the standard has the whole section (4.4 in 'USB_PD_R2_0 V1.0 - 20140807.pdf') which describes how the cable detection is implemented. In short, regular USB-A to USB-B cables need to have the special mechanical mark to be considered for >5V/>1.5A, while micro-usb send special signal on "ID" pin, and determines capabilities from that.
In theory, if you do not use special PD cable, then the devices will silently limit the maximum power to pre-PD levels, and all will be safe (at most 5V, 1.5A current).
In practice, I bet there will be manufacturers which produce very cheap cables which still claim to support maximum power, so we might still read about cheap cables catching fire.
Your initial guess is correct, ICs such as the TPS65982 handle the negotiation of power, and that one in particular handles the entire voltage spec of 5-20V.
Update
For USB-PD through micro-usb, it needs to be done through a PD aware cable. USB-OTG added an additional pin to the micro connectors (the ID pin) which is left floating on the micro-b connector. A USB-PD device uses that pin to negotiate the power profile determine if the cable is PD aware.
Your 'dumb' devices don't get damaged because USB-PD has a 'start up profile', by default it's 5V/2A (in the 1.0 version):
As the sidenote says, if you're using a 'dumb' cable (even if it's connected to a smart device), then all you'll get is 5V/1.5A.
Once a smart device is connected, however, it can negotiate a higher PD profile through the Vbus by using the PD communication protocol, which is a 24MHz BSFK protocol.
The PD 2.0 specification is a bit different. The fixed power outputs of 1.0 have been deprecated, and there are 4 nominal voltage levels with varying current abilities:
It has also been updated to include type C connectors, which as you mentioned have the CC pin, and use BMC encoding to communicate on that pin. It is important to note however that this protocol is backward compatible with the USB 2.0 devices that implement 1.0 as well.
Update 20170206
Adding new information based on Ali Chen's answer. Your device may make use of the Qualcomm Quick Charge protocol, which uses the data lines to negotiate. Specifically, the portable device puts a pair of voltages on the D+ and D- lines, and the Quick Charge IC applies a different voltage depending on whether or not the IC is configured to connect to class A or B devices. For Quick Charge 3.0, the negotiation table is as follows:
To determine if this applies to you, simply connect a USB cable that does not have data lines inside to your wireless charger or to your phone. If it reads 9V, then it's not using the Quick Charge protocol to negotiate voltage (or, at the very least, it's not negotiating over the data lines, since there could be other protocols in use). Also, and probably more effective, You could also put the D+ and D- lines on a scope, and observe the voltage changes. Here is also a state diagram for reference, taken from a Quick Charge 3.0 IC, the NCP4371:
Sources:
https://en.wikipedia.org/wiki/USB_On-The-Go
https://electronics.stackexchange.com/a/165808/17582
https://doc.xdevs.com/doc/Standards/USB%203.1/usb_31_030215/USB%20Power%20Delivery/USB_PD_R2_0%20V1.0%20-%2020140807.pdf
http://www.st.com/content/ccc/resource/sales_and_marketing/presentation/product_presentation/group0/5a/b1/8e/6c/2b/0d/46/3c/Apec/files/APEC_2016_USB_Power.pdf/_jcr_content/translations/en.APEC_2016_USB_Power.pdf
http://www.onsemi.com/pub_link/Collateral/NCP4371-D.PDF
Best Answer
From a physical connector rating standpoint, it is possible to use a USB-A port for delivering more than the standard 5V - the quick charger for my phone (HTC brand) does just that. It can provide 5V @ 3A, 9V @1 .7A or 12V @ 1.25A when attached to the phone using a USB-A to USB-C cable.
However, that particular charger is not using USB power-delivery to do so. Instead it uses Qualcomm® Quick Charge 3 (Note 1), which is a proprietary technology that is not officially part of the USB specification. It is not the same as the USB power delivery specification.
There was a power delivery extension to USB 2.0, however that was essentially just allowing USB 2.0 ports to provide a higher current (>2A), but still not exceeding 5V. That was possible based on using resistor values on the data lines to select power delivery current levels.
As far as I'm aware using USB-A connectors to deliver (or select) higher voltages is not possible under the official USB standard, power delivery or otherwise. To do so requires some other proprietary technology that deviates from the standard.
Note 1: Other such proprietary standards exist.