php is probably the way to go i'd say, partly because there are no cgi programmers available here to help you if you get stuck :P na seriously there are many pros / cons for php vs cgi but php is the easiest way, and there are the most amount of scripts for it.
yes! you can get image gallery scripts that dont use mysql, infact i expect most don't! how complex a script do you want? i.e. a page with some thumbnails then you click and get a fullsized? or one with ratings etc?
click me for image gallery scripts in php (351 scripts)
click the link and you're away laughing.