I am certain that they are all (semi) random and thought as much from the get go.
Rare would have picked out hundreds of locations and scripted a randomized spawn for them.
All of them (blue, green and red ones) are doable with two players only using swords. Granted the more help you have the faster it is.
Due to the three strikes then pause routine of the cutlass, I find it best to off-set your strikes so as not both of you hit it at the same time. This means that there is no pause on the actual statue which is when it starts healing.
We ( @CaptnJaq and I) have also taken down red ones by one person shooting at it with the blunderbuss while the other strikes it with their cutlass then (when out of ammo) change over.
Go in swinging your cutlass with full health until you see the health-bar display on screen then tap your character back a tad. Just out of harm's way, whilst still making contact with your sword slashes.
The only time it won't work is if your crew mate is a little too far back to make contact. This goes back to off-setting your slashing attack to see if you are close enough or not to do any damage.
The statue should crack with each slash of your sword, if not, you are too far away.
I like to go in even closer and take some damage as she's about to explode. It seems to speed up the process. :o)
edit: Last night another player and I found a green one under a rock ledge that we couldn't quite get to as close as most other statues.
We still managed to beat it by using swords. Just had to find the sweet spot.
