Politeness and Keigo are strongly related, but they are not necessarily the same, neither does one contains all cases of the other.
Politeness (丁寧語 teineigo) is a general term that is used for gauging the acceptability of different forms in different situations. Polite forms are expected to be used in formal situations, with most strangers, with peers you are not intimate enough with and with superiors. Polite forms don't form as coherent system as Sonkeigo and Kenjōgo do, but it's also quite simpler, since you just have to remember that some grammatical forms or expressions are polite, some are intimate and some are downright rude. We actually have the same thing in English: "Could you hand me the salt, please?" is quite more polite than "Hey, give me the salt!"
Keigo (敬語) itself, refers to the proper usage of two distinct forms of language: sonkeigo (尊敬語) and kenjōgo 謙譲語.
Sonkeigo (尊敬語) means honorific language. This category encompasses all words (mostly verbs) prefixes, suffixes, expressions and grammatical forms that are considered to convey honor to the person or group they refer to. These words are often used when referring to superiors, clients, and in some situations to anyone that is part of the recipient's inside group. Knowing in which situations one should use sonkeigo (and kenjōgo) is an entirely different question, and it's highly related to Japanese social and cultural norms, so it's natural that it seems very baffling to us foreigners in the beginning. :)
Kenjōgo (謙譲語) means humble or deferential language. This category encompasses all words (mostly verbs) prefixes, suffixes, expressions and grammatical forms that are considered to convey humility about the person or group they refer to. These words are mostly used when speaking to someone in sonkeigo and referring to yourself or to people who are in your inside group.
Very often, certain sonkeigo or kenjōgo bits are used without the entire conversation getting to stick to keigo rules. For instance, when two parents speaking about their respective sons, they may call each other's son 息子さん and their own son just 息子. You may call that sonkeigo and kenjōgo if you like (though some people may argue it isn't), but in the end the two parents might speak entirely casually. Another place you'd often find bits of sonkeigo and kenjōgo "out of place" is set phrases such as ありがとうございます (kenjōgo) or おはようございます (sonkeigo).
Don't politeness and keigo always come together?
Now, when keigo is used consistently, it's most often used with teineigo (since when you're using keigo you'd generally want to be polite), but it doesn't necessarily have to. As far as I can see, the main problem with using keigo without teineigo, isn't that it would sound rude, but rather that it would just sound too archaic.
The reason for that is that keigo was indeed used regularly without modern teineigo suffixes (of the ます and です family) during the Edo period, and you can still hear such language when watching historical films or TV dramas (時代劇 Jidaigeki). But since most people now identify these forms with the Edo period, they'd seem more archaic than they'd seem impolite. It's kinda like thou, which originally was just an intimate version of the polite you, would seem to modern English speakers more archaic than impolite.