All-optical quantum teleportation lies at the heart of quantum communication science and technology. This quantum phenomenon is built up around the nonlocal properties of entangled states of light that, in the perspective of real-life applications, should be encoded on photon pairs generated on demand. Despite recent advances, however, the exploitation of deterministic quantum light sources in push-button quantum teleportation schemes remains a major open challenge. Here, we perform an important step toward this goal and show that photon pairs generated on demand by a GaAs quantum dot can be used to implement a teleportation protocol whose fidelity violates the classical limit (by more than 5 SDs) for arbitrary input states. Moreover, we develop a theoretical framework that matches the experimental observations and that defines the degree of entanglement and indistinguishability needed to overcome the classical limit independently of the input state. Our results emphasize that on-demand solid-state quantum emitters are one of the most promising candidates to realize deterministic quantum teleportation in practical quantum networks.