Yeah, I think it has to be a magical beast.
I think a simple cold-based cone-shaped breath weapon will suffice.
The regular octopus Hide bonus based on color-changing is probably enough.
I was thinking the same on all those points, so I agree with your exquisite judgement.
Since it's basically an Octo-Jelly upsized by one category, we can just apply size advancement to the 'Jelly's abilities, give it 10 HD and convert it to a Magical Beast. That would change its stats as follows:
Octopus, Octo-Hide
Huge Magical Beast (Aquatic)
Hit Dice: 10d10+40 (95 hp)
Initiative: +1
Speed: 20 ft. (4 squares), swim 30 ft.
Armor Class: 12 (–2 size, +1 Dex, +3 natural), touch 9, flat-footed 11
Base Attack/Grapple: +10/+26*
Attack: Bite +16 melee (2d6+9)
Full Attack: Bite +16 melee (2d6+9)
Space/Reach: 15 ft./15 ft.
Special Attacks: Cone of cold, constrict 1d8+8, improved grab
Special Qualities: Blind, immunity to cold, ink cloud, low-light vision, tremorsense 60 ft.
Saves: Fort +13, Ref +8, Will +4
Abilities: Str 26, Dex 13, Con 18, Int 1, Wis 12, Cha 3
Skills: Escape Artist +11, Hide +7, Listen +9, Move Silently +11, Swim +16
plus 2 more points
Feats: Great Fortitude, Skill Focus (Hide), Stealthy
plus one more feat
According to standard advancement it should have bite 2d8 instead of 2d6, but the original has the latter.
I'd put its extra skill points in Hide and give it a higher racial bonus in that skill - it is called an Octo-
Hide, after all.
What do you fancy for the extra feat?
Should we give it the Cold subtype instead of immunity to cold?
Does that look OK to you.
All it leaves is the Cone of Cold attack.