В какой программе можно наложить на gif файл другого формата? jpeg, png или bmp, например. Чтобы в итоге и остался gif.

Эта программа называется ->графический редактор GIMP -> http://www.gimp.org/

На примере аватарки автора вопроса->
1.Изменяем холст для анимации по размеру аватарки
2.Закидываем аватарку в анимацию
3.Запускаем расширерение->"Overlay background", и моментально аватарка окажется во всех кадрах анимации
4. Сохраняем, как GIF анимацию и в результате получаем следующее->