Is this possible?
You can use GIFs just like any other format for all kinds of textures, including skyboxes.
One problem that will very likely arise with a GIF is that due to the format being "8-bit paletted" with a maximum of 256 colors (less is possible), the format is most useful for drawings, text; and in general: images that don't have a lot of colors, and more precisely: images that don't have a lot of gradients.
Which I believe will rarely be the case with the kind of images you would want to use for a Skybox (might work well for a comic-style skybox, though - also might work very well for a black skybox just having a couple of dots representing stars).
Another thing to keep in mind: Even when you use a GIF, Unity will use it's own compression (which you can select in the importer, under Texture Format). So, while there are some kinds of images where GIF will give you the smallest result with the best quality; this benefit will be lost because Unity doesn't put GIFs into the actual game (but instead a file in one of its own formats). Usually, the best format to use for textures in my opinion is therefore something like PSD because that allows you to edit your textures conveniently in Photoshop (and probably also Gimp) and in the end, what is put into the build is a perfectly compressed file format anyways (depending on what you select in the importer, of course).
As a skybox is a box with the sky projected on the sides, you would need 6 gifs to represent the sky (5 if you don't need a bottom texture). I actually have never tried it but I would expect unity to be able to import gif otherwise you could use any converter program to convert it to png, tiff or jpg first (last has lossy compression resulting in further quality loss). Gif isn't the best format for any graphics as it's 8 bit paletted so if you can get it in other formats instead (tiff, jpg, png, psd) go for them!