It is possible to get this overdrive at the very beginning of the game.

Now that that's clear, I'll try and give you some pointers. I don't know what the conditions are for this overdrive either, but just finish everything in the city up until the point Yuna is leaving Besaid (Yes, after the bonfire.) If she still won't give it to you, try talking to everyone. I got it without problems, so it shouldn't be that hard. The dog was at the temple when I got it.