You could use TTL/CMOS logic ICs to recreate an every day logic system, such as a washing machine or vending machine. Make a simple car alarm system. Or you could create a barcode reader using shift registers and AND gates to unlock a door or somthing similar. Another good project could be a digital clock, without using a 7 segment decoder and instead using discrete logic. All of these are hugely in-efficient and could easily be implimented in a microcontroller, but if your after demonstrating logic these are good examples to use.
*EDIT*
A while ago I made a single digit clock using only 4518s, 4081s, 4071s, 4017s, a 4096 and a 4511! I'm quite proud of it even though it uses 16 ICs when you can do exactly the same job with a PIC!