Quantum teleportation establishes a correspondence between an entangled state shared by two separate par- ties that can communicate classically and the presence of a quantum channel connecting the two parties. The standard benchmark for quantum teleportation, based on the average fidelity between the input and output states, indicates that some entangled states do not lead to channels which can be certified to be quantum. It was re- cently shown that if one considers a finer-tuned witness, then all entangled states can be certified to produce a non-classical teleportation channel. Here we experimentally demonstrate a complete characterization of a new family of such witnesses, of the type proposed in Phys. Rev. Lett. 119, 110501 (2017) under different con- ditions of noise. Furthermore, we show non-classical teleportation using quantum states that can not achieve average teleportation fidelity above the classical limit. Our results have fundamental implications in quantum information protocols and may also lead to new applications and quality certification of quantum technologies.