WCF Service or Web API

If you intend to do RESTful development then you will definitely want to use the ASP.Net Web Api (which was originally called WCF Web Api and created with the goal of "Making REST a first class citizen in .NET".

Another thing to consider is that the WCF REST Starter kit is no longer supported.

Note that using Web Api doesn't mean you have to use ASP.Net MVC or IIS even as it can be self hosted.

For handling operations which are non-CRUD in nature I'd recommend Googling "REST non-CRUD". I found this blog post RESTful URLs for non-CRUD operations (and particularly the comments interesting). If you decide you NEED to have RPC calls then those may have to be done with WCF. That said since WCF REST is being killed off I'm not sure what the best solution is going to be. Having both is probably the best answer but at the same time it's not necessarily a good answer.

Another alternative would be a WCF OData Service but I'm not sure if that gets any support from an iPhone.

One last point to make (that can be deleted in the future as this is time sensitive)

Microsoft has provided a Go Live license with the beta which means that it is supported by Microsoft and you shouldn't have any problems upgrading to the file RTM.

Service Stack also looks like an option.

Demos, overview, examples is available here.

There's no right answer here. You can certainly do fairly well with a WCF RESTful service. Or you could use ASP.NET MVC. Both are perfectly valid, and both have strengths and weaknesses.

Ultimately, I'd suggest you go with whatever feels the most maintainable to you.

I would like to note that MVC 4 is in beta, so watch out for bugs and don't go live until it's out of beta.