How to edit videos frame-by-frame and export in H264?

I want to edit frame-by-frame ie to the millisecond.

Am a bit confused by what you say. iMovie and QT 7 Pro are both "frame" level editors. However, some forms of editing are, by their very nature, applied over a range of frames which may be a part of your problem. In addition, since "normal" movies have frames which are spaced apart in the 16 to 42 ms range, your requirement to be able to edit to the nearest millisecond would seem unreasonable and would probably be unsupported for playback purposes without skipping 90+ percent of the frames on most platforms.

And it appears that iMovie 08 does not export in H264.

All of the "Share" and/or "Export" options (except Final Cut XML...) either default to H.264 or allow export to H.264 (or X264 if installed) video compression.

How can I edit these videos precisely and produce H264? Is there another application which would work better (and doesn't cost a fortune).

Difficult to say since you have not given any indication as to what you mean by "editing" here. You could, for instance, edit normal movie clips in a normal manner and then use an application like the JES Deinterlacer to change the playback time reference to achieve an effective 1 millisecond/frame playback rate you seem to want to target even though your platform cannot play every frame during playback.

I am editing videos of music down to the specific song I'm interested in, eliminating what comes before and after. I need the accuracy of starting and stopping at a particular frame to ensure it makes a pleasing result.

In that case, QT 7 Pro, iMovie, or even GarageBand may suit your needs depending on how extensive the edits may be.

QT 7 Pro would probably be best for simple edits. All you need to do is load the file, scrub the play head to the approximate "in" point, use the left/right arrow keys to locate the exact frame you wish to start with, press the "I" key to set the "in" point, scrub the playhead to the approximate "out" point, use left/right arrow keys to locate the exact "out" frame, press the "O" key to set the out point, select the "Trim to Selection" Edit menu option, and save or export the results.

If layering multiple audio tracks, chaptering, or audio filtering is your main goal, then GarageBand may be a better choice for editing since each track can be edited independently with regard to volume, in/out points, audio pans, audio filters, etc.

If adding titles and/or transitions, then iMovie might be your best option.

In short, you have many options and should spend some time with each application in order to determine which meets your specific needs for this series of music video projects.