Uma pesquisa rápida revelou este projeto tftpd-cgi no Sourceforge - pode valer a pena conferir.
Eu também acabei de escrever um simples servidor tftpd capaz de servir o CGI, disponível no no Github , então é definitivamente possível. Ainda não testei com nenhum cliente PXE, mas ele funciona com o cliente tftp do meu sistema operacional.
Meu uso de teste:
./tftpd-cgi.py &
echo 'get cgi/test' | tftp 127.0.0.1; cat test && rm test
Quais são as saídas do meu script CGI simples:
Hello from CGI land!
127.0.0.1:61796