Changing fan Speed of a 4pin PC case fan with a microcontroller
First of all, you are over-thinking. Solution is simpler than you think.

CPU fans are BLDC fans with four pin connector - VCC, GND, Tachometer output and Input. Here is a diagram:



Connect VCC and GND normally. Use Tachometer output to sense current speed of the fan. In most cases it will give you two pulses per revolution. So you can count those pulses using your microcontroller and get the fan rpm. 

For speed control, you need to give a PWM signal to the control pin. Here are some links that will help you learning more about it:

http://www.arduino.cc/en/Tutorial/PWM

http://www.arduino.cc/en/Tutorial/SecretsOfArduinoPWM

So here is the solution:

1 pin for tachometer (speed) sensing - You count the pulse to display rpm.

1 pin for PWM output - You use pwm to control fan speed and monitor with speed sense pin. If current speed is less than desired speed, you increase the duty cycle till both match.

1 pin for temperature sense - you define an equation or a table describing what speed at what temperature.

UART or something else for user input/output.

You can also use LCD displays for displaying the current rpm.

Edit (added some info provided by Michael Karas in the comments below)

You might want to run the PWM waveform at micro-seconds(i.e. megahertz frequency) speeds - not milliseconds(kilohertz) speeds. Optimum PWM frequency for small fan motors is greater than 25KHz. This eliminates audible frequency noise due to the PWM. It also puts the high speed on/off of the fan to much greater than the motor drive waveforms so that the PWM truly has a chance to average the voltage in the windings instead of interacting with the BLDC drive waveforms.