As far as I'm aware, Telstra don't lock the phones they sell on
contract (unlike their pre-paid phones)  So you should have no
problems using a pre-paid SIM from any network.  A pre-paid
starter pack should get you going.  You might be able to borrow
a SIM from someone using the network of your choice, just to
prove the phone isn't locked.

If you want to use the phone for data (rather than just voice
and SMS), make sure that's available with the starter kit you
buy.  You might also need to tweak some configuration settings
to use non-Telstra data services.

John