Levels 1-4

When you start out, you only have three EXP sources - catching Pokemon, hatching Pokemon and spinning Pokestops.

Catching Pokemon

At the start, catching Pokemon is very profitable - you get 100 EXP for catching, and 500 EXP if the Pokemon isn't already in your Pokedex. You can earn 10 bonus EXP if you spin the ball before throwing it, and more bonus EXP if you can hit inside the shrinking colored circle.

But all these bonuses are unreliable - most of your captures will be regular captures that give 100 EXP.

You can also evolve Pokemon if you have enough candy but don't do that until you have Lucky Eggs (see below).

Spinning Pokestops

Spinning Pokestops is a much better source of EXP. They give 50 EXP every time and refresh every five minutes. So plot a route that takes you past a good amount of Pokestops, and is about 5 minutes long. If you live somewhere like Manhattan, almost every street corner has a Pokestop and streets are 80m apart, so a regular walking pace (1.4 meters/sec) will have you hitting about one Pokestop per minute. Hop on a bike, and you can double or triple that number easy, but even without that, you're earning 3000 EXP per hour.

Of course, this cuts into your Candy supply, so stop and catch Pokemon you want, and Pidgey, Caterpie, and Weedle for evolving later.

Hatching eggs

You get one incubator to start, and can find eggs by spinning Pokestops. Every time you hatch something you get 200 EXP, plus the 500 bonus if it's new to you. Focus on the 2km eggs because they will be easy to hatch, and eggs you get now will have low CP Pokemon. Average walking speed is 5km/hr, so you can do two and a half eggs per hour of walking for 200 XP apiece. That's 500XP per hour on top of your 3000 from Pokestops.

Accounting for the 500 EXP bonuses, you should reach level 5 (10,000 EXP total) in about two hours.

Levels 5-8

You earn an Incense for reaching level 5, and another at level 7. You also get an egg incubator at level 6 and a lure module at level 8. You also earn the right to battle gyms.

Incense

Incense burns for 30 minutes, and spawns a Pokemon every 5 minutes (if staying still) or every 200 meters (if moving). Remember that average walking speed from before? In that half-hour, it will take you 2500 meters, resulting in an expected 12 bonus Pokemon encountered, or 1200 EXP per incense.

Hatching

Don't use your new Incubator on 2km eggs, because it only has 3 uses. Your XP gain will be slower, but you should make up for that when you hatch the rarer Pokemon inside 5km and 10km eggs.

Gyms

Don't bother with them. You get decent EXP for defeating Pokemon, but it takes too long and you're too weak right now.

Lure Module

Plant your lure modules on the Pokestop you plan to pass every 5 minutes on your grinding circuit.

Levels 9+

Level 9 is when you get your first free Lucky Egg, and can start doing mass evolutions of Pokemon with low candy costs. Pidgey, Caterpie, and Weedle cost 12 candy to evolve each, making them excellent candidates. You will also have Pokemon with higher costs that you can evolve during these windows to complete your Pokedex and get powerful Gym battlers.

Because each evolution has a fairly long animation, you can only do so many while your Lucky Egg is active. You have time for around 60-70 evolutions in the half-hour that the Lucky Egg is active, so make sure you have that many Pokemon ready to evolve. To make it easier, add all Pokemon you will evolve to Favorites (tap the star in the top right of their profile), and then remove them from Favorites once you've evolved them.

After finishing your Lucky Egg, send your newly evolved Pidgeotto, Kakuna, and Metapod to the Professor for more candy. Don't do it during the Lucky Egg window, it's a waste of time.

A great tip I got from my cousin is to do all your evolving while the lucky egg is on. All the +500 XP bonuses become +1000 XP.

My recommendation is, exploring a lot. By doing so, you can have plenty of pokéballs, and catch all the pokémons you see. catching gives you 500 xp for a new pokémon and candies to evolve.
Evolving gives you 500 xp (if you don't have that pokémon already) and extra 500 xp for evolving. catching lots of Pidgey or Zubats is my main xp source.

When you are level 5, train your same team gyms, so you will have a better gym and also xp reward. remember to continue exploring in order to get enough potions.

By special, there are no other ways than playing, but to catch up, you can use Lure modules on pokéstop + incense + xp eggs, that will increase the xp gain.

There's a great guide for new players that focuses on Lucky Egg + capturing first time Pokemon... but it only works on the beginning. Ignore gyms, ignore everything that doesn't yield XP! :)

On our first day using this strategy, we caught 50 different Pokémon’s which netted us a whooping total of 50.000 EXP and boosted us all the way to Level 11. Of course, this may be an extreme example as every Pokemon we caught was a new Pokémon, but still – 50 Pokemon while a Lucky Egg is activated nets you a Level 11 account with all of the rewards mentioned in the table above.

See http://pokemongohub.net/power-leveling-for-new-trainers/

And another one more advanced, focusing on evolving Pidgeys http://pokemongohub.net/pidgey-power-leveling-guide/