As answered earlier, Amaysim is the only service that allows you to search for available numbers:
https://www.ozbargain.com.au/node/201861
I wonder if there exists a service for Telstra numbers, since the number I desire starts with 049, not in the OPTUS range, which Amaysim uses.
I also heard that mobile number starting with 05 was supposed to be released this year, which should give lots of unused numbers:
http://www.acma.gov.au/Industry/Telco/Numbering/Managing-num…
On a side note, the numbers returned by directly CURL from amaysim website isn't always available.
In case of 1337:
$ curl -s 'https://www.amaysim.com.au/my-account/numbers/search_numbers_like?pattern=31337' | w3m -T text/html -dump
(*) 0403 133 717 Free
( ) 0403 133 767 Free
( ) 0423 133 723 Free
( ) 0403 931 337 Free
( ) 0423 133 715 Free
( ) 0423 133 703 Free
( ) 0423 133 739 Free
But by going to their website the available numbers returned is different.