coan.net: Nice ideas, I like the Moving Battleboats best!
Here's another: We already have Behemoth Chess, so why not Leviathan Battleboats? It would be like "plain" Battleboats (one shot per turn), except the "beast" strikes at a random square on each turn, so effectively you have two shots. The random factor means you would have to adjust your shooting pattern during the game.
pedestrian: I LOVE that idea - let the sea monster attack 1 square at random each turn.
One of the things I know I don't like about regular battleboats is it takes longer (many users like faster games), so having this 2nd square always getting attacked will also speed up the game. Plus like you said, for me - I usually follow a "pattern" to search for boats, and that would force me to adjusted continually during the game.