Yes you can do frozen fish or shrimp if they will take it. It might take a bit of trial and error. As for fresh water it will work in a pinch but is not best nutritionally. My suggestion is to mix it up. Crabs, shrimp, snails, frozen food.
As for how often every day to every other day. It depends on your octo's individual eating habits.
When I get a new octopus, especially a baby, I like to have a population of different food items in the tank for him to choose at his leisure. So far, Spike is eating 1/4" local crab babies we collected the other night. I put in at least 10 of them plus 5 small hermits and about a dozen snails. I figure as he gets established, once he depletes what's in the tank, I can start training him to know me as the "food goddess"!!
I somehow think people with the food, God, Godess thinking need to rethink their position. After keeping seahorses for several years I refer to myself as the food slave and think that is the more realistic aspect ;>)
Ya know I think you are right! I used to have an octopus, that would summon me to her tank by yanking the large 4" cleaner magnets apart, so the one on the outside would go crashing to the floor. Got me running to the tank, everytime!