Anything's possible, just depends on how much time you want to spend on it
For my animated gif, I used adobe photoshop 6.0 + adobe imageready 3.0
I made about 20-30+ frames (pretty large amount) in an attempt to make the wheels looking smooth when they move.
All you need to do is to find any sort of paint prgram that can save to gif format.
create serveral images(frames if you will) at 50x50 of cletis in a moving position, (move a little pixels here and there, such as waving or moving his mouth) in stop frame animation and find something that can create animated gifs.
then its all a matter of putting them in order, and specifiying how long each frame is shown
you can download free trial versions of
ulead gif animator and photoimpact
http://www.ulead.com/
theres many other free tools on the web methinks