If you can get a 2G iPhone off eBay (they work better than the new 3G version by the sounds of people whining on here, and look better too I think) and you are on 02 in the UK, you can go on their site, make your SIM iPhone compatible. Then they text you and you put your SIM in the iPhone and sync it with iTunes - it will be on official PAYG like mine, and you can choose to have a £10/month iPhone unltd. internet bolt-on.
You also keep any offers your SIM has, like when I top up £20 I get 500 free texts (then £10 of that goes to my bolt on, so for £20 i get unltd. internet and 500 texts) so its rather flexible in terms of tariffs.
This does NOT work for iPhone 3G - they bring that out I think in December for a price not dissimilar too a Nokia N95 on PAYG (£450). Can't complain at that, really, considering the cost of the contract.