Quantum correlations and nonprojective measurements underlie a plethora of information-theoretic tasks, otherwise impossible in the classical world. Existing schemes to certify such nonclassical resources in a device-independent manner require seed randomness-which is often costly and vulnerable to loopholes-for choosing the local measurements performed on different parts of a multipartite quantum system. In this Letter, we propose and experimentally implement a semi-device-independent certification technique for both quantum correlations and nonprojective measurements without seed randomness. Our test is semi-device independent in the sense that it requires only prior knowledge of the dimension of the parts. We experimentally show a novel quantum advantage in correlated coin tossing by producing specific correlated coins from pairs of photons entangled in their transverse spatial modes. We establish the advantage by showing that the correlated coin obtained from the entangled photons cannot be obtained from two two-level classical correlated coins. The quantum advantage requires performing qubit trine positive operator-valued measures (POVMs) on each part of the entangled pair, thus also certifying such POVMs in a semi-device-independent manner. This proof of concept firmly establishes a new cost-effective certification technique for both generating nonclassical shared randomness and implementing nonclassical measurements, which will be important for future multiparty quantum communications.