I'm based in Australia with a newly startup company in HK.  I want to
establish a bank account for this company in HK (if possible) or
overseas.  I have checked with couple of banks in HK which need one of
the director to be present in HK to attend the interview in HK to
start up the bank account.  I need to know which banks will allow me
to start an account for HK company without leaving Australia.  I don't
mind attending an interview in Australia for any bank with an office
here.

Try the Hong Kong & Shanghai Bank

http://www.hsbc.com.au/