Après la plage, une de nos coutumes préférées était de manger de la crème glacée, qu'on croyait la meilleure au monde !
This sentence is perfectly fine. It would fit perfectly well in a 20th-century autobiography or novel written like an autobiography.
The only thing I might change is to replace “de la crème glacée” by “de la glace”, although this might be due to regional differences or to changes over time. (It seems that in books, “crème glacée” competed with “glace” in the mid-20th century, then almost disappeared, and is now making a comeback. I don't know how reliable this data is though.)
Both commas are necessary, for different reasons. The comma after “après la plage” avoids a hard-to-parse run-on sentence. Many types of complements before the subject practically require a comma between them and the subject. The comma before “qu'on croyait …” is necessary for the parsing to have the desired meaning:
Nous mangions de la crème glacée, qu'on croyait la meilleure au monde.
We ate ice cream. On a related note, [implied: because we were children who didn't know anything else] we thought this was the best ice cream in the world.
Nous mangions de la crème glacée qu'on croyait la meilleure au monde.
We ate ice cream, specifically because we had reason to believe it was the best in the world. This doesn't quite give the right feeling. It's not really wrong, but it doesn't fit the tone so well.
I disagree with your teacher's feedback.
Your sentence was a bit vague as to what you were referring to (the ice cream or the custom).
Grammatically, it's ambiguous. But the meaning is clear. I think any attempt to make the grammar unambiguous would ruin the flow for no good reason.
Après la plage, une de nos coutumes préférées était de manger ce qu'on croyait être la meilleure crème glacée au monde !
This sentence is ok, but it jumbles the idea of eating ice cream with the idea that it was the best in the world. This feels more like an attempt to describe the world precisely and less like a recollection of one's youth. The grammar is fine, the meaning is fine but the tone is off.
Also, speaking of punctuation, in France (but not in all French-speaking countries), French typesetting requires a thin unbreakable space before double punctuation (:;!?) (also inside quotes « comme ça »).