EDIT: Clarified options to follow the flow of the question.
It is not possible to protect against arp spoofing on a public network if the identity of the AP can't be established and the traffic is open and not encrypted.
- What if the first arp request is spoofed, how would you prevent this ?
- What if the AP is a fake ?
Connecting and then runnig all traffic through a VPN tunnel would be the safest way to consume the public wifi, but introduces complexity and delay depending on breakout.
The most pragmatic approach would be to only use SSL/TLS, the internet scale companies is working hard to make this more secure to protect there clients for snooping etc.
The point is that it is impossible to protect against a fake arp/gateway at a public Wifi hotspot, you need to protect the traffic, and ensure you don't have a active MITM, event if the correct GW is used there can be a attack on the traffic stream behind the AP.
Some Quotes related to SSL/TLS and newer HSTS protection.
HSTS is a security policy mechanism where a Web server tells a
supporting browser that it can only connect to it over secure
connections (i.e., SSL). HSTS allows website operators to force secure
connections with users that are using an HSTS-supporting browser.
Supporting browsers include: Google Chrome 4+, Firefox 4+ and Opera
simplifies protection against cookie hijacking. e.g. Fire Sheep
the most important security vulnerability that HSTS can fix is
SSL-stripping man-in-the-middle attacks
HSTS is supported/implemented for a lot of the major internet sites, including Google, Gmail, Facebook, Twitter, Paypal. HSTS Statistics