Is secure communication without public-key crytography feasible?
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.