For me this is one of those wonderful writeups that remind me how low my skill is in comparison with people like these. Really really fascinating and inspires me to learn more about security.
A combination of skill and persistence. Believing that a one byte overwrite could be exploitable certainly helps too, more so than believing that it can’t be.
If you can’t corrupt the memory you want, find some other memory. That doesn’t work? Find something else.
Experience does help fill your bag of tricks, e.g. so that you know what patterns of malloc/free are helpful. Then it’s a “simple” :) matter of pushing all the buttons and knocking on all the doors.