Background
Jumping to Asia then Europe is known as the Kangaroo Route. Excluding that, that leaves us with flights directly to/from the Americas and Africa.
Nonstop to London is still unrealized from Sydney. Although Qantas flew London to Sydney nonstop in 1989, but that was a delivery flight. Flying Perth-London nonstop will begin in 2018 using the Boeing 787. And with the upcoming 777X and A350-900ULR, Sydney-London should be possible. What that media calls a "Kangaroo Route nonstop dream."

(gcmap.com - A330-300 typical range) Range map shows how far Australia is, for context.
Circa August 1957 is when Australia signed an Air Service Agreement with the US to operate across the USA and onto Europe. Thus securing an alternative to the Kangaroo Route. At the time planes were able to reach the West Coast of the US (with many stops) in sea planes such as the Short Solent. Even with the advent of the jet age, the 707 had to make stops in Nadi and Hawaii.
The candidates for the first scheduled non-stops are:
Africa:
On 6 January 1977, the Boeing 747SP made its first scheduled flight between Johannesburg and Sydney. The flight offered in-flight audio entertainment and movies (flysaa.com).
Contiguous US:
Pan Am:
November 4, 1982 – Pan American World Airways inaugurates service from Los Angeles, California, to Sydney, Australia; at 7,487 miles (11,979 km), it is the longest non-stop flight in the world.
Qantas:
[2014] marks thirty years since Qantas began non-stop flights between Sydney, Melbourne and Los Angeles beginning in April 1984. These services were operated by the long-range Boeing 747SP with a flying time of around 16 hours. Today, the flying time is around 13 hours.