Okay first of all, it's not Nature Power that you give the Pokémon a Berry to hold to change the moves type it's Natural Gift.
Because Eevee can only have Natural Gift by breeding, you must breed a Female Eevee with it's Hidden Ability with either a Male Phanpy, Pansage, Pansear or Panpour that knows Natural Gift, in order to potentially get an Eevee with it's Hidden Ability and Natural Gift.
There's a small chance you can get an Eevee with it's Hidden Ability from the Normal type Friend Safari.
When breeding there's a 60% chance for Eevee to pass down it's Hidden Ability to it's offspring.
If a female Pokémon has a Hidden Ability and is bred, it has a 60% chance of giving that Ability to each of its children. Each of the other Abilities has a 20% chance of being passed down.
To turn Natural Gift into a Rock type move give it one of the following Berries; Wiki, Magost, Charti or Micle.
In addition Eevee cannot learn Nature Power, although Leafeon can learn it through TM96 in Pokémon X and Y.
Sources: Eevee, Normal type Friend Safari, Natural Gift, Nature Power, Hidden Abilities
Hope I helped :)