My experiences are based on a 1080p Sharp via HDMI and an older 720p Philips via VGA and just the standard Displays pref pane (which works fine for my TV), but this might help:
First, if overscan works the same as with Apple's pref, you probably want it ON not off--off will essentially add a black boundary to the screen so that on an overscanning TV you will still be able to see the menu bar. If your TV isn't overscanning, then you'll get that black border effect.
Second, I'm assuming that since your TV has a native resolution of 1024 x 768 it doesn't have a "dot-by-dot" mode, which makes things drastically easier (essentially turn that and overscan on, and the TV is acting like a monitor with exact pixel reproduction). It's possible your TV has a "computer" mode that lets it get an exact pixel input, but if it's the same as the Philips I had, probably not (particularly with the nonsquare pixels).
1280x720 is probably the correct output resolution to set, since that should get you an image of the correct aspect ratio without shrinking the image much. (Even if your TV could accept a 1024 x 768 signal, I assume it would end up stretched due to the nonsquare pixels.) If turning overscan on doesn't get it working correctly (or, more likely, you lose the menu bar because your TV is overscanning a little, but not enough that it hides the black border entirely), you should poke around in the manual and see if it's got any way to set the amount of overscan and/or a no-overscan mode and/or the aforementioned "computer" setting. Hopefully it'll have one of those, in which case you can either turn the overscan off entirely on the TV and on on the computer, or leave it off on the computer and "zoom in" on the TV until the computer image fits the screen without borders.
You may already know this, but since I didn't and I ended up nearly getting burned by it when buying a new TV, here's a bit of a tip on what's up with overscan: Old analog TVs by necessity "overscanned"--cut off some of the edges of the transmitted picture so that it fills the entire TV screen without any distortion around the edges. You can see said distortion on many video files digitized from VHS or other analog sources without any cropping to clean it up--either a fuzzy edge, a black border, or even jagged edges.
You'd think that with HDTV and a pure-digital connection this would no longer be necessary, and it isn't, but that doesn't mean it's gone. Quite the contrary, most (to my knowledge, anyway) HDTVs--even a 1080p TV getting a 1080p signal via HDMI--still crop the edges of the image and zoom in by default. The result is a slight degradation of video quality, since you're no longer displaying pixel-for-pixel but zooming in slightly. Nonetheless, some Blu-ray discs even seem to expect this--I have some Sony Pictures discs that will have a thin black border around the edges that I assume corresponds to the standard HDTV overscan amount, such that none of the image will be lost.
Fortunately, most HDTVs do have an option to turn this off--in the case of Sharp, it's called "Dot-by-dot" mode--which lets you display a pixel-accurate image from a computer or HDMI source of the same resolution as the TV.
All this is a little different for your TV, since it has nonsquare pixels and almost certainly doesn't accept input in the native resolution anyway (at least, none of the oddball-resolution TVs I've seen, like my Philips, do), so you're not going to get a "perfect" image. But, the overscan business is still in effect, which is why you'll probably get the menu bar cut off if you can't turn off overscanning in the TV, even if you get your Mac to output full-frame video.
