Since it appears that "basic logic gates" include DFFs, it is easy to use your original idea of clocking each DFF with a different 555 output. Then all you have to do is suppress the clock to each using an AND gate (or you could actually do it with an AND, NAND, OR, or NOT gate).Sorry for the late reply! I've attached the schematic and I've also included some pictures of the circuit if that helps. I also found out that I'm allowed to use an IC if I do part of the circuit myself. So, I've made a 3-bit counter and a 3-bit BCD to 7-seg decoder for the first 7-seg display. And for the second display, I've used a 4033 IC.
Your present approach will produce a reasonable random number between 00 and 77 in base 8. You can't get, for instance, a value of 29. Is that what you want?