Most cephalopods are annual, they live breed and die in a year or less, nautilus are the only relatively long lived cephalopods i know of and no one really knows how long they live but they do live through more than one breeding cycle. Even the Giant octopus lives only a couple of years and the really large squids are equally short lived. There was a known species of octopus that lived through more than one breeding cycle but it is thought to be extinct now, it lived off the coast of Mexico and no specimens have been seen in more than a couple decades.
Turtles are long lived, CharonY's estimate is about right, the great whales are though to have long lives as well as do elephants but even the longest lived animals do not live much longer than humans.
I can see practical immortality, where the body lives on until some accident kills you. i once saw some studies that showed at the current rate of accidental death almost all humans would be killed by something other than old age well before they hit 200 years old and no one would be expected to live past 500 or so, those numbers maybe off somewhat it's been many years since i read that, but the point is that even if disease and old age were conquered death would still take us well before we reached 1000 years or more just from falling in the bathtub if nothing else....
here is a more accurate estimate of the age of animals, the bowhead whale suprised me big time...
http://en.wikipedia.org/wiki/List_of_long-living_organisms