It happened in less than 24 hours. A few minutes ago, MuscleNerd from the Dev Team posted this tweet that proves that the jailbreak for iPhone OS 4.0 is already possible.
There's a video after the break, with Cydia and Veency running on a 4.0 device. Now we only have to wait and see what the jailbreak community will come up with, considering all the features that Apple apparently "borrowed" from Cydia, like multitasking and inline spell check. We'll see.