Theoretically, the earliest you could obtain a Dawn Stone in ORAS would be after accessing the PlayNav functions of the PokeNav Plus, which is just after the player aids Wally in catching a Ralts. You could chance the GTS or trade with another player at this point, but there is also the option of Super Training. Once a Pokémon has maxed its EVs through the standard levels, you unlock Secret Super Training. The level with the Gallade balloon, titled "Those Long Shots Are No Long Shot", is the one that offers a Dawn Stone as a prize. Mauville City and the player's first encounter with Aarune happen later.
The inverse battles are more of a lottery and you only get one chance per day. Secret bases demand more effort, and you need at least bronze rank for stone hunters.