What about "cod icecream"? Doesn't it sound delicous?
Thaw frozen cod (here in Sweden they are sold in 400 g blocks in all
food shops) halfway, so that You can cut it in 5-10 mm slices, and put
in Your mouth. Tastes quite OK :-)  Be cautious when chewing because
it is cold on the teeth so te enamel might crack (problem with all
icecream) - let it rest on the toungue a moment first.

Frozen shrimps (the boiled pink ones) are a bit salty in my paleo taste
(and I avoid salt). I thaw them in cold water, wich reduces salt slightly.
I found out that it is quite possible to eat all of them, shell and
every thing. A friend of mine who has lived in west Africa told me that
they are eaten that way in Kamerun, and that Kamerun in fact means "shrimp".

- Hans