Is it possible to have 16 simultaneous PWM outputs on a 64-pin STM32F4 device?
Check for missing pins

That does look like it should work exactly as described in the datasheet.  The main thing to watch out for is missing pins on lower pin-count packages; in this case ST put a full complement of 16 pins on ports A-C and simply added new ports (D and E) for the 100-pin version.   Fortunately, none of your required pins are on ports D or E.   

Check for over-stated resources

The other thing to watch out for is designs that use muxes to share hardware.  On some micros with equivalent marketing specs there might only be four output compare units muxed between each timer.  This would prevent you from using all the features at once, but it looks like this controller has a startlingly large amount of silicon dedicated to timers and it appears that you're good to go.  

Check that this is really necessary

Do you really need 84 MHz PWM clocks?

That said, 16 PWM outputs sounds like an awful lot for most of the high-speed applications I can think of like motor control, switch-mode power supplies, and power-factor correction.  If you are in fact doing one of these things on 16 channels, then your product's primary purpose is probably to perform this PWM and it's perfectly acceptable and normal to use this hardware for this purpose.

Or can you do it with less hardware and some software?

However, 16 channels sounds more like you're dimming an array of LEDs.  If you're just dimming LEDs, then you can run your PWM at frequencies as low as 100 Hz or so, and there's little reason to utilize all this hardware for such a simple, easy task.  Use one timer and some simple (fast) arithmetic in it's ISR to control the PWM for as many channels as you like on ordinary GPIO pins.

ST went to a lot of expense to put some impressive hardware clocking silicon in this chip.  If your design is likely to go through future iterations, you should consider whether you really want to use this hardware for something as simple as making an LED glow.  You'd be using your only 32-bit timers, 4 of 6 timers with down and up/down counting ability, 4 of 8 timers with DMA request generation ability, and 8 of 18 capture/compare channels.  If you're likely to make changes or add features that might need this hardware later, it doesn't make sense to use it for LED modulation.

As I said before, though, if PWM is what you're doing, then use the hardware!