Based on first-principles calculations, we predict a half-metallic surface state in layered bulk insulator NaCoO2, with tunable surface hole concentration. The half-metallic surface has a single Fermi surface with a helical spin texture, similar to the surface state of topological insulators, but with the key difference of time-reversal symmetry breaking in the present case. We propose the realization of topological superconductivity and Majorana fermions when the half-metallic surface states are in proximity contact with a conventional superconductor.