Yes, the Arduino timing and pwm can both use TIMER0, that is why the PWM for TIMER0 has a different frequency.
The pins are not gone for normal use (output or input pin), but they are gone for PWM.
Delta_G mentioned the software PWM. Such things are often used for Servo motors, frequency outputs, and so on. It uses a single timer with interrupt. Inside that interrupt the pins are set high and low. That way every pin can have a 'software' pwm.