Still working on this. Here's the best I've been able to do so far, which at least gets him down to having to use his Captain to kill us.
Our ship:
Crow's Nest: Mate
1 (Fore): Captain's Monkey
2: Mate
3: Mate
4: Mate
5: Treachery
6: Cannon
7: Cannon
8: Cannon
9: Captain
10: Bomb
11: Bomb
12 (Aft): Bomb
We'll spot the Cannon/Pillage ship the first turn, since the challenge is to beat him even when he goes first.
1-him: He double Cannons our fore. We save the Monkey and lose our slot-2 Mate.
1-us: We Bomb his open coins. He uses his slot-12 Treachery.
2-him: He double Cannons our fore. We save the Monkey and lose our slot-3 Mate.
2-us: We Bomb his open coins. He uses his slot-11 Treachery.
3-him: He double Cannons our fore. We save the Monkey and lose our slot-4 Mate.
3-us: We Bomb his open coins. He must allow it, and loses two Cannons.
This leaves the ships in this state:
Us:
Crow's Nest: Mate
Treachery
Cannon
Cannon
Cannon
Captain
Him:
Crow's Nest: (Empty)
Cannon
Pillage
Pillage
Pillage
Black Spot
Call to Quarters
Captain
Captain's Monkey
Broadside
I think the most obvious play would continue like this:
4-him: Use Cannon to attack Treachery, which reacts to take the Cannon with it.
4-us: Sacrifice crow's nest Mate to kill fore Pillage.
5-him: Pillage fore Cannon.
5-us: Move fore Cannon to Crow's nest and double Cannon his fore, killing fore Pillage and Black Spot.
This leaves things like this:
Us:
Crow's Nest: Cannon
Cannon
Captain
Him:
Crow's Nest: (Empty)
Call to Quarters
Captain
Captain's Monkey
Broadside
Cannon
At this point, randomness enters into the picture, because I think the obvious next play for our opponent is this:
6-him: Move Black Spot to crow's nest and use Call to Quarters.
However, it doesn't really matter what he gets, because he can arrange like this:
Crow's Nest: Cannon
Captain's Monkey
(Random Coin)
Captain
Broadside
6-us: Double cannon, destroying his (Random Coin), with the Monkey saving itself.
7-him: He Cannons our fore Cannon.
7-us: We must Captain his crow's nest Cannon, or it will kill us next turn.
8-him: He Broadsides our Cannon.
8-us: We Captain his Broadside.
9-him: He Captains our Captain.
I still think there's a solution, I just don't have any more time to work on it tonight. 
Feel free to jump in anywhere in the above, if you've got an improvement.
(Incidentally, what have been your results when you use this ship against itself?)