Without the GD image library you're going to have a very hard time working with images. I know it's possible to use the gimp for image manipulation through server side scripts, but chances are if your host doesn't provide GD, then they're not going to let you do this either.
Besides, if your host doesn't provide it, you probably need to find a different host. I've never seen a pay host that didn't have it. Some hosts have newer version of the library, which is nice, but nearly all hosts will have it.
GD also supports many other graphic manipulation/creation functions and supports JPEG/PNG and possible more (not gif though).
GD supports JPEG, PNG, BMP, and a pseudo image type GD.
I have a script on my site that does this very thing, and uses the GD library. Check it out here: http://gagon.net/phpimg/. Let me know if you have any questions about it, or would like to see the source.