I'm thinking of building another mythbox (slave backend and HDTV capable frontend) for as cheap as I can. I don't need it to do 1080p, just 1080i and 720p, What is the weakest processor I can get to handle these resolutions in the following lines:

Athlon 64 (My guess is all of them would be fine?)
Athlon XP
Sempron
Pentium 4 (what minimum Ghz with and withouth hyperthreading)
Celeron D

I'd like to do it without XvMC but if you have know a low end processor that will work with XvMC I'd like to know about that too. I will most likely use nvidia 5200, 6150 or 6200 graphics.

I can do that with an Athlon XP 3200+ with nVidia 5200. I think you can go lower though.

I have an athlon xp barton @ 2ghz and when playing 720p h.264, cpu usage is about 76%

You'll want the 5200 video card. XvMC creates a grayscale OSD on all nvida cards but the 4 and 5 series. I'm using an athlon 64 X2 3800+ (2Ghz) and am able to record standard def with an old wintv card, hi-def with a dvico card, and watch a recording simultaneously. I have a 6600 and don't like the grayscale OSD, so I'm not using XvMC. When doing this, CPU is at about 80% so any other heavy multitasking is pretty much out of the question. I bought the 6600 before I knew about this limitation and the price difference between the 5200 and 6600 was negligable.

I would say with XvMC, and no standard def you could go much lower on the CPU requirements. Recording using an analog tuner that doesn't have a hardware mpeg encoder uses quite a load of CPU.