In Civ3, instead of making a real leaderhead, a one could quickly whip up a flag in place of it.

My question is, how easy would it be to do the same in Civ4?

trivial. They did it in the mods that came with the game. Just need to make an appropriately sized texture. Photos are an option too.

Its simple, you just need to make a 256x256 image and then convert it to dds(type doesn't seem to matter, but i've been using DXTC5 just to be safe). Once you have the image converted you need to edit the Assets/XML/Art/CIV4ArtDefines_Leaderhead.xml file, the <Nif> section of each leader. Just point it to where your new dds file is.

If you need a dds converter, heres one that converts back and forth and lets you view them. http://www.amnoid.de/ddsview/download.html