T-Mobile will sell you prepaid service at $100 per 1000 minutes/SMS messages, or pay-as-you-go for $30-40 per month without a contract. I have service for my G1 via the latter option, which costs me about $75/mo. with unlimited data and more calling minutes than I can conceivably use.

My experience has been that most carriers will happily let you sign up for some sort of prepaid service without a contract, as long as you don't expect hardware discounts.