What is the earliest level that a cleric can create an intelligent / self-willed undead creature?
A PC cleric can create an intelligent undead by level 2 or 3; an NPC cleric must wait until level 3 or 4
A PC Clr2 that possesses a Wisdom score of 16 and the feat Scribe Scroll can work alongside a Clr11 to create a divine scroll of create undead (6th-level spell at caster level 11). Such a scroll requires the Clr2 to make a Spellcraft skill check (DC 16), normally takes 2 days to create, and has a price of 1,650 gp, but this price is halved to 825 gp because the Clr2 makes it himself (with assistance,obviously, and assuming the Clr11 provides the spellcasting service (normally costing 660 gp) for free).
The Clr2 also must contribute the price of the spell's material components—50 gp per Hit Die of undead to be created—, and, given that after creating the scroll the Clr2 has only 175 gp of his 1,000 gp wealth by level remaining, the Clr2 will likely only be able to muster at most a 3 Hit Die undead like a huecuva (with its sad Int 4; and the Clr2 has but 25 gp for his adventuring gear) or a 2 Hit Dice undead like a ghoul (Int 13; and 75 gp, respectively).
To cast the spell create undead from the scroll, the Clr2 must make a caster level check (DC 12), but the Clr2 can make this check repeatedly without expending the scroll.
With wealth by level of 3,000 gp, a PC Clr3 can take this route legitimately without needing to convince the Clr11 to provide his services for free.
With their reduced wealth, NPC clerics must wait until levels 3 (normal NPCs) or 4 (heroic NPCs) to follow a similar route.