We present a scheme for correcting qubit loss error while quantum computing with neutral atoms in an addressable optical lattice. The qubit loss is first detected using a quantum non-demolition measurement and then transformed into a standard qubit error by inserting a new atom in the vacated lattice site. The logical qubit, encoded here into four physical qubits with the Grassl-Beth-Pellizzari code, is reconstructed via a sequence of one projective measurement, two single-qubit gates, and three controlled-NOT operations. No ancillary qubits are required. Both quantum non-demolition and projective measurements are implemented using a cavity QED system which can also detect a general leakage error and thus allow qubit loss to be corrected within the same framework. The scheme can also be applied in quantum computation with trapped ions or with photons.