Did you, by any chance, purchase an ATmega328 instead of the ATmega328P used in all the Arduinos? The 'P' (Pico-power) version has a different signature.
He should set to verbose output (in preferences) to obtain exact signature bytes. If it is zero or not.
What model Arduino are you running the ArduinoISP sketch on? One of the page you link to is for an Arduino Micro.
Did you select "Arduino as ISP" (not "ArduinoISP") from Tools->Programmer before selecting Tools->Burn Bootloader?
"avrdude: Device signature = 0x000000"That tends to indicate a wiring error. The wiring will somewhat depend on which model Arduino you are using for ArduinoISP.
Has the ATmega328P you are programming been set to expect a crystal? If so you have to provide a crystal or an alternative clock. Adafruit has an alternative version of ArduinoISP that uses Arduino Pin 9 for an 8 MHz clock output. You can connect it to pin 9 (XTL1) of the ATmega. https://github.com/adafruit/ArduinoISP