I'm a newbie, but I've actually simulated a few simple things in electronic workbench (from basic sequential and combinational nets such as FFs or MUXs to 8-bit shift-register, full adder, CLA...) completely based on Boolean algebra and logic gates, as an exercise (not very advanced, mind you, but still an exercise). So, with a risk of being completely wrong my opinion on hand-made logic-gate-level ROM is:

the easy part
1) To write set of equations required to do address=>byte function is not at all hard. Simple table [address|content] and you're off.
the not so easy part
2) To write automated minimisation process (Quinne McClusky for example) is a little harder but attainable. If you are familiar with the method it can take a few hours, if you have to get familiar a day or so.
3) To do 'post minimisation optimisation' based on your chosen 'logic base' (and or not/nand/nor) is also a tricky part, but can be done, or you can skip it altogether with a risk of having redundant gates in your design.
the disqualifying part
4) Based on size of ROM (more than handful of bytes) you'll get pretty large combination net. To accommodate average bootloader you can get enormous net in number and dimensional sense!
5) ANY error whatsoever that is hardware-coded is IMPOSIBLE to overcome easily, so ANY error WILL cost you dearly.
6) ANY change of code (new functionality for example) is, again, IMPOSIBLE.

Possible more appropriate solutions:

1) ROM/... Why avoid some kind of ROM? It DOES address=>content function. It IS it's function, or am I completely wrong here? I still fail to see why you opt to use logic-gate-hardware instead od ROM?

2) FPGA as mentioned and you'll get your function. Even if you are not familiar with, it can be beneficial to acquaint yourself with it since it has very versatile usage...

Both methods give you easy code=>hardware transitions and (usually) can be reprogrammed if anything goes wrong or if you want to improve your circuit.

Best luck,
CN