For $75, Burner Phone will ship you a "completely anonymous" phone set up for 30 days of use. The only caveat: you then have to eat it.
Just kidding, you can throw it away. The payment system, which requires a credit or debit card, seems a weak link. Even if Burner Phone destroys their records, the banks won't. Also, you have to trust Burner Phone, and, presumably, whoever that dude is in their domain's DNS.
Update: Bitcoin support's coming soon, the creators say in a thread at Hacker News. [Thanks, Fredley!]