Consider enlarging the board, or using TSSOP devices (which I guess at this speed, should be 74HC for some, and AC or LVC when needed?).
While it's usually possible to route a board with minimal space left between components, it's not a pleasant option. Expect to commit about half the area to routing. Routing as highways and streets may be helpful: make small blocks of tightly coupled components, then arrange those blocks near each other according to their connections, and so on hierarchically until done. For each step, leave a gap between blocks, proportional to the size of that block. That way you end up with one big gap down the middle of the board (where long distance signals and buses can be routed), smaller gaps feeding that, and smaller gaps feeding those. You always have enough room to route an average number of signals this way.
Don't be afraid to rip up and try again. Swap gates, swap components between blocks, swap blocks. Adjust boundaries (the blocks probably won't be exactly the same sizes, after all, making this fractal concept a lot uglier in practice). Adjust priorities (which signals take the "right of way" as it were, with the least interruptions / bends / vias), and adjust routes (take a different "street" around this or that block, etc.). Adjust positions again to shove components closer, taking up what free space is left.
If you're still new at this, just one go at the layout may take weeks; seasoned, days. Don't be discouraged; even a rip-up is still learned experience, whether in using the tool, or in understanding the relationships between components and pins.
Board outline -- if you're stuck to a particular board size, consider using riser boards, or stacking. Same block-oriented concept, put stuff behind connectors of modest size. (BTW, alternate signal and ground in a one-row header, or assign one row of grounds in a two-row header.) Or, synthesize all the damn logic in an FPGA and be done with it a lot sooner.

(Again, providing one has the experience; if not, expect to spend a few months learning what VHDL or Verilog is, and how to use it.)
Tim