When was the concept of the FPGA invented?
Before the "FPGA" with either EPROM (Altera, 1984) or SRAM (Xilinx,1985) there were families of programmable logic, where the programming was done by blowing fuses on-chip to break unwanted connections.

This was a one-way process; you can't un-blow a fuse, so these were generally "use once" devices, though sometimes you could ensure that any design changes you made were blowing additional fuses.

These were generically called PLDs - Programmable Logic Devices - though the first specific brand were known as PALs - Programmable Array Logic. I've seen claims from AMD marketing that they invented these - not technically correct, though they bought MMI (Monolithic Memories Inc) the company that did.

PALs were usually a much simpler structure than FPGAs, generally a comprehensively interconnected network of AND-OR gates, with or without registers on the outputs - you broke the connections you didn't need. Each could typically replace 4-8 TTL SSI or MSI packages, a useful saving in board space, and reduced the number of board design changes required.

AMD came along with the more complex but more flexible PAL22V10 a little later, then after a few years, went on to buy MMI.

Programming was usually with a low level HDL - usually PALASM or  CUPL - to generate a programming file listing the fuses to be blown. Then insert the chip into a programmer and load the file...

I think the first PALs were available from MMI around the mid 70s, and popular by about 1980. In addition to the MMI databook (1978 onwards) there was a Systems Design Handbook (my 2nd ed was from 1984, can't find online) was a collection of application notes covering basics all the way up to audio spectrum analysers, and, like the handbook, mainly notable for a series of cheesy cartoons...

  

The schematic for an entire chip, unprogrammed, looked like this:


And a program (in this case, one of MMI's own examples, for a 4-bit counter), in PALASM looked like this...


Pretty basic, but easier than marking the fuses you wanted to destroy on the schematic above...

Note the two lines starting "CLK" ... they are names for the pins in order, numbered from 1 to 20. These correspond to the schematic above (which doesn't show pins 10 = GND or 20 = VCC, which are predetermined). Comparing this with the schematic you'll see that CLK and /OC are also predetermined, and all the other input pins are on the left, outputs (registered) on the right. 

Also note that this design is for a 16R6 but it'll fit a 16R8 because pins 12 and 19 (which are unregistered in the 16R6) are unused - i.e. NC - in this design.

In practice you'd probably use an off-the-shelf counter like the 74163 instead, unless it was Saturday and Stores was closed, or someone else had goofed the polarity of the Load input.

Some more info here...

And for some perspective on work in that era, see "The Soul of a New Machine" by Tracy Kidder - the book mentions the advantages of a newly available form of programmable logic, and the timeframe pretty much means it has to be PALs.

Following on from these were mask programmable devices, much larger, but much less amenable to small scale development - notably the Ferranti ULA, which made the BBC Micro and Sinclair ZX81 possible around 1982. These offered a few hundred or a few thousand gates. Like mask programmable MCUs, you sent off your paper tape, got a thousand parts back aftel 6 weeks, and prayed that your design and testing had been thorough enough...