Indeed. 1000 simple CPUs will fit in a FPGA, though it might require one near the top of the line. (e.g., picoblaze reportedly needs 96 "slices" and 1.5 "block RAMs"; the biggest Virtex-7 FPGA has more than 1400x as many block RAMs and 3100x as many "slices") There's little doubt that you could program a DCT for a picoblaze, if you wanted to.

It's hard to tell what 5.0GBps refers to -- the bitrate of the incoming, uncompressed, RGB video data? If so, that's maybe about 800FPS of 1080P video. In a circa 2002 paper, FPGAs were doing 100FPS HDTV DCT; an improvement of only a factor of 8 in the intervening 8 years would be frankly disheartening. Especially given that DCT of a frame of video is embarassingly parallel. The FPGA I mentioned earlier could hold 180 copies of the DCT from this paper; right there you have 18kFPS without even raising the clock. But the multipliers can probably also be clocked faster now...

You've just described the FPGA. Large areas of an FPGA are devoted to thousands of almost-identical functional blocks ("slices" in xilinx parlance). For instance, in one Xilinx family, a slice contains a 4-input LUT, a flip-flop (1 bit of memory, called an FF), and other specific gates that help implement things like carry chains, shift registers, and some 5+input functions the chip designers thought were commonly encountered.

Other areas contain "block RAMs" and "DSP cores" (basically, dedicated multipliers).

But now you've got yourself a lot of hard problems to solve: how to dice a program into something that is represented by essentially LUTs and FFs. how to recognize when a special function outside the LUT, like a carry chain, should be used. how to efficiently route the signals from where they're produced to where they're consumed. how to actually implement an efficient LUT where the contents are field-programmed. how to figure figure out what speed to clock the whole thing at so that it operates properly. how to read in the configuration to the chip. This is an enormous investment in research and software, and you still have to target the chip with languages that are totally alien to your typical C/C++ programmer.

As far as I know there is no production FPGA that you can write software for without using proprietary software. (though often the software can be obtained at no cost, at least for the non-flagship FPGA chips) This is partially because the details of bitstream structure are trade secrets of the respective FPGA companies, but also partially due to the inherent difficulty of the task.