As I said in the original post, Project64 can do it, specifically Jabo's graphics plugin. I had though Rice's plugin for Project64 could do it as well (and could have sworn I played Zelda with aspect ratio corrections, hi-res textures, and FSAA on my 25:16 monitor) which is why I originally addressed this toward Mupen and not just the plugin but after firing up a Windows machine as I couldn't get Rice to work with Project64 under WINE, I don't think it actually can.
Non-4:3 aspect ratios are not part of the N64, but neither are high-res textures, so there is some precedent for doing things to help make the graphics nicer beyond the original capacity of the N64.
As far as the fake backgrounds in Zelda (ands other games), those are stretched, but the true 3D parts (and UI) in those areas are rendered properly, and full 3D scenes just have more of the world rendered and look very nice. IMHO, this is nicer than either stretching the entire scene or pillarboxing it. Since some people might not want / think this, that is why making the aspect ratio match the screen is an option.