I know you can adjust the horizontal position of the image in the Gamecube's system menu. But from the sound of it, your TV just might be too old. It's happened with my TV. As they get older and more hours are put into them, they tend to "warp", often blowing up the image slightly and cutting off parts of the screen. For example, I was playing Super Mario 64 the other day and after I beat Bowser, the text for Peach's thank you at the bottom of the screen was almost completely cut off.
It's not enough to really ruin a game for me, so I can live with it for now, but from the sound of yours, it might just be time to get a new one.