I put a few variants on a little book, "Giocare con carta e matita". There is an English edition by Sterling ("Mind Sharpening Logic Games", formerly "Super Sharp Pencil & Paper Games") but some games are missing, Battleship among them. If you are interested in that kind of games, have a look: there are 40 of them (50 in the Italian and Czech editions by LDC and Portal respectively) with several variants.

One Battleship variant is similar to one already quoted: it is the one where you fire 7 shots all together, and the answer is the number of hits (not which ones are hits). You also tell which ships are hit ar if they sink. For example: "5 misses, an hit on a battleship that sinks and a hit on an aircraft carrier." You can also mix it with the variant in which you reduce the shots when you lose ships (that I knew as an independent variant - you shoot one shot for each ship you have at the moment).