a tefl certification (TESOL or CELTA) will help, but more importantly are the following:
1: You are a native english speaker, and you don't look asian.
2: a PGCE (will help, but if you answered yes to the above, you should be ok).
Have a check on the hong kong government's website for their native english teaching programmes, because you better start applying within the next few months.
Currently, with the state of the Hong Kong education system, schools have been given extra money to employ TEFL teachers, but I would actually say that there's greater competition for places now, and they are actually in the process of reducing class sizes and possibly closing a small number of schools.
Still, don't restrict yourself to schools only. There are many tuition centres that regularly employ NETs at the moment and at better salaries than public schools (just be prepared to work on a Saturday, or Sunday, or both!).
Good luck in Hong Kong!