I've been developing my own method for randomizing a coastline from a basic outline. This method may have been discussed on here before, but if it has, I haven't seen it in my frequent perusal of the tutorial threads. This method is for Gimp, but it should be pretty transferable to PS, if I remember my PS stuff at all. I'll try to write this tutorial so that anybody can follow it, but if you have questions, don't hesitate to ask.
We begin with a basic, smooth coast outline, land in white, water in black
I find things work out best if you use the pencil tool with a hard edge, but feel free to experiment. If you have no ideas for this, I believe there are a few good tutorials somewhere out in the guild that give nice results for basic coastlines.
Next, we need a noise layer. Click the 'new layer' button in the layers dialogue (if you don't have this dialogue open, you can find it in the 'dialogue' menu on the top of your image). I usually name this layer noise, but you can name it whatever. You can just create this layer filled with transparency, since we'll have the computer fill it in.
In the filters menu, choose filters>render>clouds>solid noise, set the detail to the maximum, and generate a new seed.
The size sliders should be set to the same value, but what that value is is entirely up to you. I find that this method works best with larger sizes. I have provided several screenshots of results of different size noise layers later so that you can judge the effect.
Next, duplicate the base layer with the rough coast outline (the duplicate button is also on the layers dialogue), and move it to the top. Now, we want to displace the coast, so again go to the filters menu and select: filters>map>displace. Now, in the window that appears, set displacement mode to polar and edge behavior to smear. The numbers for pinch and whirl are relatively arbitrary, so I suggest playing with these to get results you like. No matter what these numbers are, you should select your newly created noise layer in the dropdown slider next to each of them.
When you click 'ok', this should create your random coast. Picture 4 is an example of a coast created with the maximum noise size, picture 5 is with a smaller size.
I hope that was clear. If anybody has any questions, please don't hesitate to ask.