i am not sure at what kit you are looking at. I believe the native Apple one will not display the menu on the TV screen, just the movie, so you could only do blind navigation.
I think the current classic ipod may not even support that, I noted that the "Touch" specs explicit note that it can output 480p but for the classic it does not.
Did you consider just getting a mini mac? It's a bit more expensive but you also get much more (i expect it to be updated before christmas). For older mini macs you can get ATV4mac (Tiger/Intel only, not the current Leopard OS).
Are you after the movie rentals? Or do yo just want to play your own content?
BS9000, BS2300, BC2, BL2500, BL3, Bl2, BS1, BV8, BC4, A8