I have $N$ coins all showing heads. At each turn, I change the state (i.e., a head is changed to a tail, vice versa) of $N-1$ coins.
I already proved #1.
For #2, my conjecture is $N$ steps. The only proof I can think of is to show that $N-1$ steps are not enough. But this gets me nowhere.
On
Let $H_k$ denote the number of heads that are showed after $k$ turns. It depends on the actions that are taken, but some general things can be said. We have $H_0=N$ and $H_1=1$ and next to that it can be verified that:
$$H_{k+2}\in\{H_k-2,H_k,H_k+2\}$$
This combined with $H_0=N$ and $H_1=1$ implies that we can only reach $H_k=0$ for some $k$ if this $k$ is even and $N$ is even (your first problem). If the conditions is met (we start with an even $H_0=N$), if $k$ is even and $H_k>0$ then $H_k\geq2$. This makes it is possible to end up with $H_{k+2}=H_k-2$. In the first move we leave the state of a coin showing head untouched and in the following we leave the state of a coin showing a tail untouched. That such a coin will be there is ensured by $H_k\geq2$.
So going from $k$ to $k+2$ you can loose exactly $2$ heads. This confirms that your conjecture ($N$ steps, where $N$ is an even number) is correct.
Number the coins $1$ through $N$. For $k=1,\ldots,N$ let $f_k$ be the action of flipping every coin except coin $k$. Performing $f_k$ twice has no net effect, no matter how many other flips intervene, so a minimal solution will apply each $f_k$ at most once. Let $K$ be the set of $k\in\{1,\ldots,N\}$ such that $f_k$ is used in some particular minimal solution; $|K|$ is then the total number of flips used in that solution. Each coin whose number is in $K$ is flipped $|K|-1$ times. Each coin whose number is not in $K$ is flipped $|K|$ times. The numbers $|K|$ and $|K|-1$ cannot both be odd, so ... ?