Strictly speaking, he could have done it on April 13th. The real question is when it would be politically sensible to do so, and in my opinion its hard to create the right combination of circumstances much earlier than in our timeline. To make the EP viable, the following conditions need to be met...
1. A fairly extended Southern Insurrection: Remember that, for most loyal citizens, the war was not about ending slavery: it was about preserving the Union, the integrity of the idea of a free, constitutional republic, ect. If the war looks like it can be ended early (Say, unlikely as it may be, an 1861 march on Richmond), the Proclamation won't just look unessicery, but likely to harden rebel resolve and extend the war for an Abolitionist pet project. Its only as the war drags on that its likely to be accepted as a war measure.
2. A turning point (or at least something that can be spun as one) towards victory: Ultimately, the "threat" of Emancipation isen't likely to work if the rebels feel like their winning, and would look like a desperate, empty gamble to potential intervening powers (IE Great British) if the timing isen't right. To get this as early as possible, a wolleping of the Army of Northern Virginia in auteam of 1861 or early spring 1862 is likely your best bet
3. Possession of fair chunks of enemy territory: To emancipate slaves, Union military forces need to be near areas with large numbers of slaves to emancipate. Your best bet here is probably Tennessee refusing to secede and/of Kentucky wholeheartedly joining the cause from the get go. An early strike down the plantations dense Mississippi lands would make the idea of contrabands appealing from a labor point of veiw.
4. Possession of a fair chunk of contrabands: In a rather amusing tidbit, the EP also is needed to maintain the moderate Republicans' legal assertion that the rebellious states have never left the Union, as otherwise by not returning runaway slaves loyal generals were violating the law of the land; the Fugative Slave Act. This is actually probably the fastest way to getban early EP. Have rump "Restored Governments" (a LA West Virginia) form for rebelling states by loyal citizens complete with with representatives in Washington near the war's beginning. Have them raise that thorny issue in front of Congress, and you might get an EP proposed to head off Radical Republicans.