We like to start campaigns at 1st level for the reasons that High Lord Dee stated and 99% of the characters get to 2nd or 3rd providing they don't do anything to stupid.
About last april I moved to a bordering state so sadly had to leave my decade+ group of gaming buddies.
Luckily one friend from that group is a sales rep and where I live now is part of his territory so he comes into town about once a month or so for 2-3 days and we get down with some serious solo sessions with his cahracter.
Due to our infrequency of play and keeping with a fast and furious on the go narrative I bump him up a level after an adventure (2-3 nights) or partway through a long adventure.
I try to keep the adventure contained enough and easy enough to wrap up that we can finish so we aren't waiting a month or so to continue.
This style of level advancemet works great for us and I think compliments the Mongoose suggested Howard style narrative.
When I moved back in April he was 5 th level. He is now 10th.
My player likes it, I'm cool with it and we do not feel that the character has suffered for it(sounds crazy but you get the picture) and were having a blast!
Of course if I was back to playing every Friday night with a larger group I would go back to awarding XP.
Last year the party fought in a couple large scale battle as we tested out the mass combat rules (PDF not FC). Afterwards instead of awarding XP I gave everyone a free level of Soldier and adjustd their XP from the next level accpordingly.
No one complained, a couple players were kinda quitly thinking it over at first but quickly thought that it made sense since they had just fought in a couple battles and they did not sacrifice any hard earned XP for it. And as mentioned we were testing out the rules.
One of the barbarians is the character of my friend who comes into to town. Normally a hardcore single class guy with no intentions of multiclassing. His character was going to stay to his roots not to be tainted by civilization.
But now he has totally gone multi class crazy and picked up another level of soldier, a couple thief and 1 pirate. Sounds kinda familiar actually except he is from the Black Kingdoms not Cimmeria.
Now he likes being more civilized and being paid well by kings for his work and spending it all etc...!!
So really you can do just about anything you want depending on your situation and the players think its fair.