I'll start by answering the second question: suppose that every single triple is weighed. Then, if all of the coins had their position in the order subtracted from 2000, then every reading would still be the same, but every coin except the 1000'th would have their position changed, so would have two possible positions. Now for the first. Weigh first coins $A, B$ and $C$, get a huge piece of paper and write down their positions, where say WLOG $B$ is the middle, put $A$ on the left, $B$ in the middle and $C$ on the right. (1 weighing so far). For the next coin $D$, weigh it with $A$ and $B$. If $A$ is the middle, then put $D$ to the left of $A$, and if $D$ is the middle, put it between $A$ and $B$. If $B$ is the middle, then weigh $B$, $C$ and $D$ - if $C$ is the middle, then put $D$ to the right of $C$ and otherwise $D$ goes between $B$ and $C$. (Maximum 3 weighings so far). Now, suppose that you have written down $2k$ coins on the paper. Get coin $L$ (say the next coin unplaced) and weigh it with the coins in positions $k$ and $k + 1$ on the paper. If $L$ is in the middle, then put it there, and otherwise, say if $k$ is the middle, weigh it with $L$ and $k - 1$. Now, each time that the newly introduced coin is middle, swap the old non-$L$ coin for the coin on the other side of the newly introduced one (so, if say $k-1$ is in the middle, swap $k$ for $k-2$ and reweigh), and if $L$ is in the middle then place it between the other two coins on the page. This is unless the other two coins were 1 and 2 (or $2k-1$ and $2k$ in the other direction), in which case place $L$ on the edge. At any rate, the maximum number of weighings performed was $k$. Now, suppose that you have written down $2k-1$ coins on the paper. Use the same strategy as before, starting at $k-1$ and $k$, for a maximum number of $k$ weighings (and this can only occur if $L$ is on the left, not the right). Starting from having 3 coins written down, do this for all coins, until you have an order for all of them. This will mean that the total number of weighings carried out is $2(1+2+...+999)-1 = 998999 < 1000000$. Simply take the coin in the middle on your sheet, and you're done.

Unless I am dumb, it seems to me that you can do much better than this: If you have already determined the order of $n-1$ coins, you can repeatedly divide the interval where the next coin ends up essentially in half, by first starting in the middle, then starting in the middle of the remaining interval (unless already done) etc. This way it seems that for the $n$-th coin we need at most $k-1$ operations if $n \le 2^k-1$. This way we end up with a safe algorithm of length \[1+4 \cdot 2+8 \cdot 3+16 \cdot 4+32 \cdot 5+64 \cdot 6+128 \cdot 7+256 \cdot 8+512 \cdot 9+976 \cdot 10=17953\]which is significantly less than $1000000$. (In asymptotic terms it means that we can order $n$ terms in roughly $n\log n$ operations, rather than $n^2$.)

Tintarn wrote: Unless I am dumb, it seems to me that you can do much better than this: If you have already determined the order of $n-1$ coins, you can repeatedly divide the interval where the next coin ends up essentially in half, by first starting in the middle, then starting in the middle of the remaining interval (unless already done) etc. This way it seems that for the $n$-th coin we need at most $k-1$ operations if $n \le 2^k-1$. This way we end up with a safe algorithm of length \[1+4 \cdot 2+8 \cdot 3+16 \cdot 4+32 \cdot 5+64 \cdot 6+128 \cdot 7+256 \cdot 8+512 \cdot 9+976 \cdot 10=17953\]which is significantly less than $1000000$. (In asymptotic terms it means that we can order $n$ terms in roughly $n\log n$ operations, rather than $n^2$.) In fact you can also do this in $\mathcal O(n \log_3(n))$ operations. I could give the details if anyone is interested. This "makes sense" since each time you query a triple you end up getting $1/3$ of the information. There are $6$ possible permutations for three variables and fixing the middle one gives you $2$ options. This gives that $1/3$ factor and so you "should" be able to solve it in $\log_3(n!) \sim n \log_3(n)$.

Hint