I am almost certain that, as an Australian citizen, I will need a visa to visit Russia - that is not a problem. Is it possible to do a solo tour through these regions of Russia? What kind of transport is available - ferries, buses, trains (I do not drive). Is there a travel pass available?
Doing the sites on Kamchatka or Sakhalin on your own is possible but but personally I would not recommend it without good knowledge of the language and lots and lots of time.
To get to Sakhalin you could take a ferry from Vanino problem is you have to get to that port first. The same company provides cargo service from Vladivostok to Petropavlovsk-Kamchatskiy so you might be able to hop on one of their freighters.
There is a discussion on a DROM(Russian) regarding transportation from Vladivostok. But it also includes some pointers for the tours locally.
There are tours organized by local tour operators into various places on Kamchatka including Valley of the Geysers and various other tours with the cost running from ~$500 to ~$1000 or more. Do they provide tours in languages other then Russian? Possibly but then cost will likely rise some more.
For Sakhalin I'd probably start looking from the SakhRest(Russian) portal which provides a decent starting point and some links to the resources you might need to get around the island and see some sites.
P.S. One thing to point out. This is not exactly a foreign tourist hot spot, so I would suggest that knowledge of Russian is a must.