I think I have came up with a quite handy technique to make a rough coastline in Photoshop.
I apologize and reserve myself of inventing something old here!
I also apologize for my bad English. I'm from Sweden.

I think this technique can be used on any sized maps.

Here is the step by step tutorial.

1. Select your land (layer one) (right click on the layer - select pixels)
2. Select - Modify - Border - I used 5 pixels on my 11000 x 8000 map. Point is to select how much of the coastline shall be affected.
3. Refine Edge - Slide "Shift Edge" to 100% to make the border solid
4. Keep the selection and make a new layer (layer 2) above the land layer. Edit - Fill... - White (doesn't really matter which color you fill with)
5. Enter the "Layer Style" in the new layer - Pattern Overlay - Blue Daisies 50% Scale (Or depending on how rough the coastline shall be)
6. Now, merge down the new layer. Honestly, I haven't figured out how to merge down one single layer with an effect, so I simply create a new (layer 3) blank layer - select the blank layer (layer 3) + the layer with the pattern (layer 2), and "Merge Layers".
7. Now you shall have two layers - Your land (layer 1) and a new daisy-coastline layer (layer 2)
8. Image - Adjustments - Threshold. I try to get around 50% white 50% black here.
9. Magic Wand - Select either the black or the white, "Contiguous" shall be unchecked.
10. Hide layer two (the former daisy-layer) and select the Land-layer.
11. Delete once, and you get a very rough coastline. Now Deselect your selection.
12. Select Pixels on your land layer, and then hit Refine Edge
13. Refine Edge - Here you need to play around with the values. I used "Smooth 2", "Shift Edge 50%" and "Contrast 100%". Everything else is just "0"
14. From now on you can smooth up the coastline after your own liking.
15. Deselect everything, then select your coastline once again.
16. Select - Modify - Expand 1
17. Select - Modify Contract 1
18. Edit - Fill... - Foreground color
19. Reselect your land (layer 1) and Edit - Fill... - Foreground color once more
20. That is pretty much it. I'm sure you can mix around more in every step to get a better result. Maybe try another pattern, a different threshold or another "Refine edge" values.

Good luck!