There is a left luggage counter in the center of the arrivals hall. Rate from a year ago was HK$50 for 3-24 hours.
There are no hostels in northern Lantau near the airport. Technically, there are some on the southside, but those are for hikers or local vacationers to overnight in Lantau. Not convenient at all to get to from the airport.
If you don't mind spending a little more than those questionable private hostels in the city, consider these three hotels in Kowloon run by non-profits: Caritas Bianchi Lodge, Salvation Army Booth Lodge - these two are next to each other, very convenient; and the YWCA Anne Black House.