Hi adelphysi,
The Arduino Uno is more than capable of implementing a flight controller, even using float PIDs.
You just need to use the hardware I2C bus to the gyro on analog pins A4 and A5, preferably running at 400kHz.
You also need to use analogWrite() on digtial pins 3, 9, 10 and 11, as these run the PWM at a frequency of 490Hz, that's required to drive the ESCs. The 50Hz generated by the servo library too slow and in any case is software based so is prone to jitter.
Joop Brokking's videos on Youtube are a good starting point for any flight controller design.