How did handheld video games from the 70's and 80's work?
While the 4004 and Z80 were available, they were both unlikely to be used in handhelds where low part count, cost and battery life were important. 

There were families of 4-bit and 8-bit microcontrollers from the 1970s that have been mostly forgotten - these usually had on-chip ROMs so after developing your program on a relatively expensive emulation system - always in assembly language - you paid your money and the silicon manufacturer made a mask - and printed YOUR specific ROM contents on a waferload of blank chips, then tested, sliced and packaged* them : six weeks later you had a delivery of 25000 micros with permanent ROM contents and prayed that the program would work...

(* Or supplied die for you to fit your own epoxy blob over)


Texas Instruments had the TMS-1000 and sold probably millions with the same damn set of 20 slightly-off-key tunes for doorbells. 
National Semi had the SC/MP ... don't know much about it except that I believe it was used in the first Sinclair computer, the "Science of Cambridge MK14", a year or two before the ZX80, ZX81 and Spectrum.
Intel had the 8048 eight-bitter that may still be used in PC keyboards as far as I know ... they even had an EPROM version (8748) which appealed to the smaller company (no mask costs! YAY!) I was bitten when the promised CMOS version of the 8748 was quietly dropped...
Zilog had (still have, I think) the Z8.
Motorola, oddly, kind of missed this boat despite the 6800 - the 6802 may have been an attempt but the 6811 was (to my recollection) quite late in the game.
RCA had the CMOS (low power!!!!) 1802 with the weirdest instruction set on the planet.
And a long-forgotten company called General Instruments had another offering, which my "Preliminary" datasheet from 1983 calls the PIC1652 or PIC1654 (with 256 or 512 words of program ROM.) and a fairly freaky instruction set. I expect that sank without trace...