Is secure communication without public-key crytography feasible? We all know about public-key cryptosystems, and we know some of these are computationally secure (for the time being, of course).

Are there any algorithms out there which allow safe communication between peers in a non “public/private” key fashion? If so, I would like to know some of these. If not, does any kind of formal demonstration of the infeasibility of such algorithms exist?
The obvious answer is symmetric keys.  You'll find that this is actually what asymmetric keys end up used for, exchanging symmetric keys.  If you trust someone who gives you a key, and you can trust that no one else has it, that's about as secure as it gets.  The difficult of satisfying those requirements is why we have asymmetric keys.