cgi-bin stands for common gateway interface binaries. you can write applications in just about any language (perl, c, python, ruby, even applescript) that are called via the webserver. these scripts can do pretty much all of the things that php can except mix in html... all html output in a cgi script has to be done via echo() or printf() or similar. cgi's often don't have automatic processing of get and post data or cookies and the api those languages have is usually not as well suited for web programming (ie, things like urlencode() often have to be done manually).
php and other inline scripting languages were developed for a reason... writing cgis is a royal pain!