Actually, you can get Headbutt even before Julia. You just have to catch a Bidoof and level it to 15. Then you trade it to the man in the house to the right of Mosswater Factory for a Litleo. Litleo will already have Headbutt as a move as it learns it at Level 11. Since Bibarel will be Level 15, you also get the bonus of Noble Roar.