Constant Sum Voltage Divider With Thermistor/Temp Sensor

You can accomplish temperature feedback by connecting the analog voltage out pin of the TMP36* to pin 5 of the 555. A temperature increase will increase the voltage at pin 5 of the 555, this increased voltage will increase the "on" time of the 555 as I've outlined elsewhere. This will, in turn, increase the voltage that the fan is experiencing and thus its speed! You will need to tune the size of the potentiometer and capacitor to suit the application.

*Connect the other two pins to \$V_\text{cc}\$ and ground according to the datasheet.

Yes – simply use your external DC voltage to bias the feedback voltage. Done! (this means connecting it, with a appropriately sized resistor, to the threshold pin).

I'm not trying to make my life difficult

Well, still you're using a NE555 to generate a PWM. I'd simply go, get a cheap microcontroller with an ADC and a PWM unit (these start well below half a Euro), write ten lines of C firmware and be done. No analog circuitry you have to tune, no uncertainty and non-linearity of duty cycle as function of control voltage, just clean software in a microcontroller that doesn't need any external components but a decoupling capacitor for its power supply. Bonus: internal oscillators of microcontrollers these days would usually be much more accurate than a NE555.

Update better late then never: you mentioned you're not allowed to use microcontrollers. I know this will probably mean some learning overhead, but a CPLD-implemented PWM generator with either a resistor-ladder-based ADC implemented with pins and external resistor networks (so you don't have to solder a lot of resistors) or a cheap ADC IC would still be what I'd use. PWM is basically a pretty digital problem, so I'd go digital.

Another easy approach would simply use a quad Opamp IC: Opamp 1 & 2 to generate a triangle wave, opamp 3 to compare the instantaneous triangle voltage to your external DC voltage. Easy PWM, and gotten rid of the NE555.