I've seen 3 turn pvp wins (I was on the losing end :p) and I've won in 5 turns against halfbloods/false gods, so based on that, 2 turn wins vs ai0 should be very easy with immorush and similar decks. Turn 1 might be possible with an absolutely perfect hand. Something like the deck that laxadarap posted but with chaos powers for the ball lightnings might be able to do it, as I've seen that kind of deck do as much as low 20s on the first turn for damage, and so if it topdecked something good on turn 2, it could kill an ai0 then.
I might have to try this when I get home tonight... :p It would make for a pretty funny screenshot.