The polynomials obtained from (1) are the normalized Legendre polynomials. For all three cases, it is possible to calculate them by hand, but (especially for (3)) the calculation can be quite cumbersome. So, I've used the following Mathematica code for the Gram-Schmidt (including normalization) procedure:
Clear[f, g, ip];
ip[f_, g_] := Integrate[f*g*1, {x, -1, 1}];
proj[g_, f_] := g*ip[f, g]/ip[g, g];
normalized[f_] := f/Sqrt[ip[f, f]];
gs[fs_List] := Module[{u}, normalized /@
Table[u[k] = fs[[k]] - Sum[proj[u[j], fs[[k]]], {j, 1, k - 1}],
{k, 1, Length[fs]}]];
lps = Expand[gs[Table[x^k, {k, 0, 4}]]]
This is the code for the first part of the question - if you want to do it for (2) and (3), just replace the part in the second line after f * g with the appropriate weight function and the correct interval.
For any inner product there is indeed a unique (up to scaling) polynomial $f\in P_{n+1}(x)$ orthogonal to $P_n(x)$ (the space of polynomials of degree less than or equal to n).
To see this assume (seeking contradiction) that $f, g$ are linearly independent polynomials in the orthogonal compliment of $P_n(x) \leq P_{n+1}(x)$. Note $\{1,x,x^2...x^{n+1}\}$ form a basis of $P_{n+1}(x)$ so this is an n+2 dimensional vector space over your field.
Suppose $f,g$ are linearly independent. By Gram Schmidt WLOG they are orthogonal. Then $\{1,x,x^2...x^n,f,g\}$ are $n+2$ linearly independent. This is a contradiction since it implies $dim (P_{n+1}(x))=n+2$.
To see the above set is linearly independent note $1,...,x^n$ are manifestly independent. f and g are independent of each other by assumption. Suppose:
$$\sum_{i=0}^n{\lambda_i x^i} = a f(x) +bg(x)$$
Then taking inner products on both sides with f and g implies $a = b=0$.
Best Answer
If you want to build Legendre polynomials manually (we wil use the interval $[-1,1]$ and normalise them to get $L_p(1)=1$), you can use the following procedure (note that $p$-th Legendre polynomial has degree $p$).
1) zero degree, $L_0(1)=L_0$, hence $L_0(x)=1$.
2) first degree, $L_0\bot L_1$, $ L_1 (1) =1 $. We take $L_1(x) = ax+b$, so we can write
$$0=\int_{-1}^1L_1(x)L_0dx= \int_{-1}^1 (ax+b)dx= 2b,$$hence $b=0$.
Next, $$1= L_1 (x) =a x $$ so we can take $a=1$.
3) second degree: $L_2(x) = ax^2+bx+c$, you impose orthogonality to $L_0$ and $L_1$ and normalise it to $L_2(1)=1$. This will give you three linear equations on $a$, $b$, $c$, which we are able to solve.
This iterative procedure gives all $L_p$. This wiki article gives many properties of Legendre polynomials, take a look at it.