Turns out Xcode was never actually free: previous major releases were synchronized with OS releases. Xcode 2 came with 10.4, Xcode 3 came with 10.5.
The reason why they were "free" and Xcode 4 is not is... that Xcode 4 has been released "mid-cycle" before Lion landed. Previous Xcode were "paid" through the OS they came with, even if you downloaded them from Apple's website as it was the OS entitling you to the relevant Xcode install.
With that said, where are we so far on Xcode?
* Since Lion has not been released yet, all macbooks but Air come with the standard DVD set which contains an Xcode install
* Xcode 3.2.6 and the iOS 4.3 SDK are still available as free downloads for the Air (or to replace older Xcode installs), just go into the dev center and you are given a link to Xcode 3. You even get a download link for Xcode 3 from the Xcode 4 page: https://connect.apple.com/cgi-bin/WebObjects/MemberSite.woa/...
I understand that people kind-of freakout (I did originally), but if you actually look at the events with a cool head, and previous devtools-related-events (as well as previous instances of Apple's wonky SOX-related decisions), it seems extremely likely Xcode 4 will go back to "free for everybody" on Lion, it might even be an at-install option (à la OSX Server).
Oh yeah, and there are already binary distributions of OSX compilers: http://llvm.org/releases/download.html has both Clang and LLVM-GCC binaries for OSX.