通常はカードの期限が切れる1-2か月前に銀行から新しいカードが郵送されるはずです。新しいカードを受け取っていないなら、すぐ銀行に電話するか直接窓口に行って事情を話した方がいいです。
新カードを受け取っていない理由としては、引っ越したのに銀行での住所変更手続きをしていない、貴方またはNZ Postがカードが入った郵便物を紛失した、誰かがカードを不正に入手した、口座自体に何か問題がある(例、長年使用していないため休眠口座になった）等が考えられます。

直接行くときは、トピ主さん自身の証明書類の提示を求められると思います。期限切れのeftpos カード、身分証明書（パスポート、運転免許証）、住所証明書（現住所に郵送された電話や水道の請求書、賃貸契約書、現住所と名前が宛名として書かれているCouncil や病院などから来た手紙　等）等を持っていくことになると思いますが、トピ主さん個人の事情によって違うかもしれませんので詳しくは銀行に確認してください。

ちなみに、「カードがなくても窓口で引き落としたり出来るか」という質問ですが、貴方が間違いなく口座の持ち主であることを銀行に証明して、必要な手続きが終了すれば引き出せます。当日引き出せるかどうかは、状況次第かと思います。