Conectar Arduino a Internet (NO LAN)

1- Cómo puedo conectar un arduino a Internet? He visto post que usan un Ethernet Shield, pero tengo entendido que eso se usa en redes LAN. También leí de usar una tarjeta SIM y enviar SMS a un teléfono, pero tampoco me satisface. Lo que yo quiero concretamente es enviar datos a un servidor a través de internet.

Creo que la pregunta no esta bien formulada teniendo en cuenta lo que afirmas en el párrafo.
No sabemos si tu dispositivo esta fijo o será móvil.

Si es fijo necesita o WIFI o una conexión Ethernet a una red local.
Si es móvil, y esta dentro de cobertura WIFI podria ser una opción sino, requiere de una conexión celular.

No hay muchas opciones. Podríamos hablar de radio pero eso requiere de cobertura y muchas veces enlaces opticos o sea que los puntos antena y móvil se vean. Algo no muy fácil.

2- Qué módulo de GPS me recomiendan?

Si usas un módulo SIm, hay versiones como el A6/A7 que tienen GPS y capacidad de enviar datos por celular.
También esta el SIM808/908 que hacen lo mismo.