I want to report back with my Nest learning thermostat and millivolt escapades. In case it is useful to someone.
tl;dr: I made it work. But indeed, Nest doesn't support millivolt use cases well enough for it to be the only thermostat.
Quick run-down of facts:
Found this nice presentation which, if you look down the pages, contains a reasonably detailed block-schematic of the switching and power connections for the Nest. The block diagram is detailed enough that you can draw meaningful conclusions about which approach may work. The schematic says, for example, that when heater is actuated, Rh and W1 terminals will be shorted. This is exactly what we need to actuate a millivolt system - the only concern is whether the short circuit that the Nest circuitry makes is "millivolt enough" to cause the correct reaction. Turns out, it is.
Connected a 24V AC adapter to the C and Rc terminals. This provides power to the Nest device. The block schematic says that the C-Rc combination will allow Nest to get power. It also seems that this power will not be electrically coupled with Rh in this particular wiring configuration, which seems important.
Connected the millivolt wire terminals to Rh and W1 on the Nest backplate. The wires will be shorted to actuate, so either way of wiring wil be is OK. The block schematic says that there is a FET switch which will short the two terminals when actuated, but otherwise keeps them open. Apparently the voltage drop across the FET is low enough that our stove considers it as a short and actuates.
The schematic seems to indicate that Nest senses the wires mechanically. This means you need to use either solid core wire, or tin the terminals that go into the backplate so that they compress when clamped down by the latch. Stranded wires will spread and flatten the conductor cross-section so much so that the mechanical switch will think there's no wire. I was lazy to tin the terminals, but I instead removed a longer piece of insulation from the wires than minimally needed, and then folded about 1/8in of the wire onto itself and jammed that in. It was enough to make nest think that the wire is there.
Nest is battery powered, so in theory it could use battery power to actuate the heater during power outage. However, Nest's software prevents this - you get some error code which says that power is out - and it may well be for a good reason. The end result is, you can't use a Nest learning thermostat if power is down in your home. This matters a lot to us, since we live in the mountains where power outages are not unheard of, and the propane stove that Nest controls can and should work without power. I ended up leaving the old mechanical thermostat connected in parallel to the Nest, just in case. So when power is out, you simply use the old thermostat. For the "regular" Nest operation, when it controls an electrical heater, a power outage is irrelevant, since when power is out to the Nest, the power is out also to the device that it controls.
I still worry about the Rh terminal floating but haven't yet measured what happens.
YMMV, based on the type of the device that you are trying to control. Some people have reported what seems to be this exact setup as non-working.
I also bought a 24V AC operated mechanical relay to insert in case it is necessary, and as advised elsewhere. I tried to find a solid-state relay but couldn't find one which is correctly rated - they seem to start at over 40V and all I found are DC - which makes sense, but is worth knowing. I ended up not using the relay. Note that in case of relay operation, your wiring must be different.
Once the above is handled, the rest of the Nest setup went basically without surprise.
Hope this helps. I think this is more detail about this setup that I could ever find on the Internets at one place.
Some colleagues at work advised me that tinning stranded wires isn't the best idea since the tinning is soft and can flatten over time and then confuse the mechanical wire sensing in the Nest learning thermostat, and they recommended putting an actual connector terminal with a wire crimp. I was too lazy to do that now that our setup works fairly well, but this is something to consider if you are following the instructions above.
Be very, very aware that the instructions above are specifically for the thermostat that is called "Nest learning thermostat". This is, as it were, the most expensive Nest thermostat out there. There are other, cheaper models, for which my colleagues reported failure to control a millivolt thermostat. The Nest learning thermostat is some $250 at the
time I write this; but given how much propane it saves us, it has already paid itself off during the winter. Nest-E won't work this way.
Note also, the Nest learning thermostat does not officially support millivolt systems. I think this isn't related to whether it is possible to do, but rather related to the fact that Nest can not work without external power, so your Nest would be useless in a power outage. Since millivolt devices can usually operate without power (like a propane stove for example), and are installed in places where power may be flaky, it is expected that the thermostat can operate them without power too. But Nest can not deliver on that - the battery power simply isn't enough for this. As you can see above, I worked around that issue by keeping the old mechanical thermostat connected in parallel.
Hope this helps.