Sorry, but the only real way to level up a Pokemon is to face off against some strong Pokemon and win. It will be tedious and boring, but if you REALLY want that salamance it'll be worth it. The best way to go about doing this is facing/re-facing the elite 4, but if you're not up for that, head to your local victory road and run around in a cave or tall grass, and battle every Pokemon you see. A good way to go about doing this is putting shelgon at the front of your party, get into a battle, and switch it for a much stronger Pokemon, so it still gets exp. Another option is using an exp share or a lucky egg, or both, or just give everyone in your party one of them, and win some battles to see the exp pile on. If you're in a gen 5 game, theres audino, which gives REALLY high amounts of exp when defeated, but rustling grass is unpredictable, so use it when necessary. Finally, you can use all the rare candies you own on your shelgon. You might not have much, but it'll save time in the long run.
(I don't normally condone this, but I want to cover all the options: You can also cheat/hack, but if I were you, I'd waste the time and get an honest to goodness salamance.)
And wow that was long, but there you go! Good luck!