You could start off on a one tile island. With a slow tech pace, the AI might never get to Amphibious warfare and even if they did, i don't think they use marines very well.
You could pop a warrior with a scout from a barb hut, use it to conquer an AI city and keep it, allowing you to then go on to play as usual, taking AI cities (or not) to win. Alternatively, does the Inco start with a Chasqui scout who could get lucky and take an AI city...