I started off same as you mostly doing storyline and events (just enough to get into the storyline missions) as a Mesmer and it was tough. Looking back I probably would have had more fun if I got higher levels before doing the story and not kept dying in storyline all the time. Definitely I recommend you get a level advantage before doing story!
If you have the gold and materials you could do some crafting for some fast levels (can level even up to 80 in maybe 1-2 hours? just google the many available guides to gw2 crafting).
You could also find an event train or champ train commensurate to your level (should at least be able to tag enemies with enough damage before they die to get credit).
A really fast way to level would be to join a big group in World vs World or Edge of the Mists which features the 3 following shortcuts to leveling:
1. Daily keep take - when available for the day, taking a keep with the group yields a book that will give you one full level up.
2. Karma training - If the group has evolved into a full blown zerg it's gonna roll over all resistance and plow through enemy towers and keeps which gives a continuous stream of exp and goodies. (just never separated from the group or you might get picked off by enemy roamers)
3. Big fights - the rewards are considerable but you should be joining these only when you have enough damage dealing ability to tag enemies and enough survivability (i.e. escape skills like stealths, teleports or overall toughness) because if you are running the usual glass cannon build you will most likely become rallybait (you will get targeted as killing an opponent in WvW can rally ALL of your opponent's downed friends.)
Well whatever you choose have fun! :)