It's possible to make animated GIFs that use more than 256 colors per frame (although they'll probably be bigger than a format designed for that sort of thing).
Technically, I believe, you're still limited to 255 colors per frame- you can just put two frames with two different sets of 255 colors on top of each other with 0 delay. :)
Not quite: Each image descriptor has its own Local Color Table, but the delays aren't set by the image descriptor, they're set by the Graphics Control Extension block, and you can have multiple image descriptors per GCE block. So the GIF can look something like: HDR(GCT) GCE(delay10) IMG(LCT) IMG(LCT) IMG(LCT) GCE(delay10) IMG(LCT) IMG(LCT) IMG(LCT) ..., with several image descriptors per frame, each with its own palette.
However, due to historical reasons (GIFs optimized for old browsers on slow computers), modern browsers sometimes insert a small delay between image descriptors even if they're in the same frame. I generally consider this a bug. However, there are many broken GIFs out there...