One of the Strongholds in my world (generated in 1.6.4, currently playing in 1.8) is under the seabed. On reaching the seas near the stronghold, I discovered guardians. There are no Ocean Monuments nearby (nearest one I know of is about 2000 tiles north of the stronghold). I can confirm these are spawning here and not moving here from somewhere else; I switched to peaceful, made sure the guardians did despawn, then switched back to hard difficulty, and observed guardians spawning in the water above the stronghold.