In the end it's all about a very simple equation: E(kin) = ½mv² so it's all about exhaust velocity. The closer you can get that to its theoretical maximum (e.g. c), the less reaction mass is required.
But the question still remains: is there a practical non-Newtonian way? We already know of rather impractical ones, such has deforming spacetime.
I've wondered if it would be possible to build an efficient rocket engine that accelerates its reaction mass so hard that it gains an appreciable amount of relativistic mass? The fundamental problem with interstellar travel is the amount of reaction mass you need to make the trip in a reasonable amount of time. The rocket equation is a harsh mistress. If you were accelerating each gram of propellant so hard that it gained a metric ton of relativistic mass you could bypass it, assuming you had some sort of lightweight yet near limitless power source.
But the question still remains: is there a practical non-Newtonian way? We already know of rather impractical ones, such has deforming spacetime.