polynomials - Inverse for a permutation over GF(2)

I very much doubt there is a formula for the inverse of a permutation. As far as degrees are concerned, I expect most permutations and their inverses to have degree $n$. A caveat here: the degree is not well-defined for functions in $GF(2)^n$ as e.g. $x=x^2$, but it is if you require all monomials to be squarefree. Then all functions can be represented by polynomials of degree at most $n$ and most of them have degree exactly $n$.

Your second question does not make sense. If $g(x_1,ldots,x_{n-1})=f(x_1,ldots,x_{n-1},0)$ there is no guarantee that $g(GF(2)^{n-1})$ is contained in the subspace $x_n=0$ of $GF(2)^n$ (which is where $f$ takes its values).

Edit: I just noticed that, for $n > 1$ a permutation has degree at most $n-1$, so I amend my guess to say that most permutations and their inverses have degree $n-1$.

The degree bound follows from the fact that a coordinate function of a permutation takes both values $0,1$ the same number of times and from the fact that the coefficient of $x_1 cdots x_n$ of such a coordinate function is the sum of its values at all points of the domain.

Edit 2: (in reply to the comment below)

To compute the inverse, interpolation might be reasonable. Another way is to use the above observation on the coefficient of $x_1 cdots x_n$. So, for instance, the coefficient of $x_2 cdots x_n$ in a polynomial $p$ is the sum of the values of $x_1p$ which is also the sum of the values of $p$ on the points with $x_1=1$ and so on. I don't see a way to use the fact that we're dealing with permutations to improve on these methods.

As for your second question, if you assume $f$ preserves both $x_n=0$ and $x_n=1$ then I think the last coordinate of $f$ is $x_n$ and the same is true for the inverse. Then the highest degree occurs elsewhere and the inequality you want on degrees is obvious.