I quite like my Nokia E65 which is a small slider phone, offers quad band GSM/GPRS/EDGE, and 3G (WDCMA2100 in Europe), WiFi (802.11b/g) and bluetooth.

it does have a VOIP (SIP, not SKype) client for internet phone calls, and you can tether it to the nokia tablet over bluetooth /edit/.

data calls on non-specialised contracts are expensive, but T-Mobile generally offers the best deals with "web-n-walk".

your best bet for making cheap internet phone calls is to stay at a hotel which offers free or cheap wifi - Best Western are one of the few hotel chains which do this!