1. Use AMIDST to generate a map from a seed. It can be any seed, but you should memorize it.
2. Search the map for a village in the desired location. If no villages seem to be near coastline, start over.
3. When you find a seed that creates a coastal village, create a creative map using that seed. You can fly to the village if it's close to spawn, but if it isn't save and quit.
4. Open the same map in AMIDST (open from file, not create from seed).
5. Teleport Steve to near the village you want to investigate and save his location.
6. Go back into the map and check it out... see if the village is everything that you hoped for.
Sometimes AMIDST generates false positives, and there won't be a village there, but usually there is.
Sometimes you might want to check out several villages per map.
Eventually you will find something worth pursuing.
It might take a couple hours, but it works. I generated my current favorite map with this method. The key is that AMIDST lets you rapidly search thoroughly through maps, letting you move on to a new seed very quickly until you find a promising map.