As long as you want to use 2D graphics it is rather simple.
Convert your graphic into .dds. I think it has to have a height and width of 2^n, for example 512x512 pixel. You'll also need a smaller version of the same image with 128x128 pixels.
http://www.imageconverterplus.com/download/
places a watermark on your image, if you use the unregistered version and
http://eliteforce2.filefront.com/file/DDS_Converter;29412
gave me very blueish images. There are probably better tools available.
Open C:\Programme\Firaxis Games\Sid Meier's Civilization 4\Assets\XML\Art\CIV4ArtDefines_Leaderhead.xml with a texteditor. Immediately save the file to the corresponding folder of your mod.
Ctrl+F and search for the name of the leader you want to replace the graphics. You'll get an entry like this:
<LeaderheadArtInfo>
<Type>ART_DEF_LEADER_ALEXANDER</Type>
<Button>,Art/interface/LeaderHeads/Btn_LH_Greece_Alexander.dds,Art/Interface/Buttons/Actions_Builds_LeaderHeads_Specialists_Atlas.dds,1,11</Button>
<NIF>art/LeaderHeads/Alexander_the _Great/alexander.nif</NIF>
<KFM>art/LeaderHeads/Alexander_the _Great/alexander.kfm</KFM>
<NoShaderNIF>art/LeaderHeads/Alexander_the_Great/alexander_noshader.nif</NoShaderNIF>
<BackgroundKFM>art/LeaderHeads/Alexander_the_Great/alexander_BG.kfm</BackgroundKFM>
</LeaderheadArtInfo>
Change the entry to:
<LeaderheadArtInfo>
<Type>ART_DEF_LEADER_DEIN_LEADER</Type>
<Button>Path to 128x128 image/Name of 128x128 image.dds</Button>
<NIF>Path of 512x512 image/Name of 512x512 image.dds</NIF>
<KFM/>
<NoShaderNIF/>
<BackgroundKFM/>
</LeaderheadArtInfo>
The path is relative to your modding folder. For example Art/Leaderheads/Grafik.dds
Save and start Civ.