Build: You don't have to have MR on every item you buy. Getting at least a little armor is almost essential; I recommend Zhonya's. Spirit Visage is practically core on him because of his ability to heal himself + the MR becomes AP. Abyssal Scepter also synergizes with Galio extremely well.
You don't have to be the best last-hitter in the world as Galio. The first few levels, when you don't have the mana or AP (converted or not) to clear waves with a single QE combo, can indeed be a drag. Galio's base AD isn't that bad... Just work on your last hitting in general. If you think your lane opponent is going to beat on you too much during your attempts to CS with your autoattacks, level your shield first. Survival>CS and kills. Keep in mind that Galio tends to build more tanky items that raw damage, meaning his items can be cheaper and easier to build.
Galio doesn't require you to build nothing but AP and MR to be a major source of damage; his bases damages are decent and his scalings are strong. If you learn to land your ultimate at the proper times, you'll do less net damage than a Ziggs would by spamming, but you'll net kills for your team because they get free damage in on the enemies you taunt.
I'd suggest getting Rod of Ages over Righteous Glory; you already have a speed boost on your E and a boost to your resistances on your W. RoA isn't one of my favorite Galio items, but it does work well with him... It just delays his other items while only giving raw stats. You don't need Catalyst's sustain after you get your Chalice of Harmony; your W provides extreme sustain (try using it on yourself and walking up to meet new enemy minion waves; the minion attacks will heal you a lot).
Don't fret about not being a DPS machine when you play Galio. You're a godlike tank with plenty of utility and damage, but you need that Chalice to get rolling.