Como poder se puede, pero es muy raro, te va a llevar tiempo, y capaz te queda un código bastante propenso a errores. Además ningún shared hosting te va a permitir ejecutar programas compilados como "scripts" cgi, en todo caso deberias tener un vps o dedicado.
https://www.cs.tut.fi/~jkorpela/forms/cgic.html http://www.boutell.com/cgic/
Habia visto otra libreria como para usar CGI con C pero no me acuerdo el nombre ahora!
