Si existe el IC con 4 NAND, es el 74LS00, en cuanto al 64 te puede servir pero recuerda que ya tiene conexiones internas, es decir todas las and tienen su salida conectada a la NOR
Y definitivamente los retardos no te perjudican para nada en una comunicacion a 9600 incluso apostaria a que puedes llegar a 115,200 sin problemas....