"PNG geht nicht" ist keine sehr umfassende Beschreibung deines Problems.
PNG ist das einzige Webgrafikformat, das Alphatransparenzen unterstützt, und daher dein einziger Ausweg. Leider kann das aber der IE/win nicht anzeigen (Opera, Mozilla, IE/mac schon) -- aber auch dafür gibt es
einen Trick.
GIF kann Transparenz nur in dem Sinn: Ein Pixel ist entweder 100% durchsichtig, oder 100% färbig.