Have your Golbat hold a Soothe Bell during battle. If you can afford some, give it some vitamins. I don't recall where exactly you get the soothe bell(maybe the flower shop in Goldenrod?), but I know you can get it fairly early. I had my Golbat evolve into Crobat by level 24, after fighting Morty. It shouldn't take terribly long.
Yesterday I started off with a level 2 Zubat who evolved into a Crobat right at 23 (a level after having evolved from Golbat). What I did was equip it with a Soothe Bell, give it a haircut in Goldenrod (Zubats have hair?) and then ride up and down Goldenrod on your bike for about a hour or two.
Periodically check with the woman in Goldenrod (she lives in the house near the bike shop), she'll give you responses that tell you how close your Pokemon is to reaching max happiness when it's in the first slot of your party. Here's a link to the list of phrases: