For the first part we can use Euler's $F-E+V=2$, where $F$ is the number of faces (counting the face that includes $\infty$), $E$ is the number of edges, and $V$ the number of vertices.
If there are no triangles then each face is enclosed by at least $4$ edges. So $4F/2<E$, i.e. $F<E/2$. From this we get $V>E/2+2$. If all vertices have order $\geq4$ then $4V/2<E$, i.e. $V<E/2$. From this we get $0>2$. So, we cannot have no triangles and at the same time all vertices with degree $\geq4$.
For the second part take a vertex that has degree $\leq3$. Color it and its neighbors with different colors $A,B,C,D$. We can do this only because it has degree $\leq3$. We can delete this vertex and the edges insident on it. If we color the rest of the graph there is always a way to color the deleted vertex. Notice that the graph with this vertex deleted still has no triangles, but less vertices. Apply induction on the number of vertices now.
There are many ways to construct triangle-free graphs with large chromatic number. One well-known construction is Jan Mycielski's, which is described in the Wikipedia article that you cited; I guess you had trouble understanding it. Instead of explaining Mycielski's construction, I will describe another one, which is even less "efficient" (meaning that it produces a bigger graph for a given chromatic number) but maybe slightly simpler.
For a given natural number $n\in\mathbb N$, let $G_n$ be the following graph with $\binom n2$ vertices and $\binom n3$ edges: the vertices are the pairs $(x,y)$ of integers with $1\le x\lt y\le n$; for each triple $(x,y,z)$ with $1\le x\lt y\lt z\le n$, there is an edge joining vertex $(x,y)$ to vertex $(y,z)$. It is plain to see that $G_n$ is triangle-free. I will show that $G_n$ is $k$-colorable if and only if $n\le2^k$. Therefore, if $2^{1525}\lt n\le2^{1526}$, then $\chi(G_n)=1526$.
First, suppose $G_n$ is $k$-colorable; I will show that $n\le2^k$. Let $f:V(G_n)\to[k]=\{1,\dots,k\}$ be a proper vertex-coloring of $G_n$; i.e., for $1\le x\lt y\le n$, the vertex $(x,y)$ gets color $f(x,y)\in[k]$. For each $x\in[n]=\{1,\dots,n\}$, let $S_x=\{f(u,x):1\le u\lt x\}\subseteq[k]$. Note that, since $f$ is a proper coloring, the sets $S_1,\dots,S_n$ must be distinct; namely, if $1\le x\lt y\le n$, then $f(x,y)\in S_y\setminus S_x$, showing that $S_x\ne S_y$. Thus there are $n$ distinct subsets of $[k]$, i.e., $n\le2^k$.
Now, suppose $n\le2^k$; I will show that $G_n$ is $k$-colorable. Let $S_1,\dots,S_n$ be $n$ distinct subsets of $[k]$, indexed in order of increasing size, so that $|S_1|\le|S_2|\le\dots\le|S_n|$; it follows that $S_y\not\subseteq S_x$ whenever $1\le x\lt y\le n$. Finally, we get a proper coloring $f:V(G)\to[k]$ by assigning to each vertex $(x,y)$ a color $f(x,y)\in S_y\setminus S_x$.
Best Answer
Let me elaborate on my comment. Assume we have some polynomial algorithm 3COL, which returns a valid 3-coloring 3COL(G) of any triangle-free 3-colorable graph $G$ in polynomial time.
As 3COL is polynomial there are some $a,b,c \in \mathbb{N}$, such that on a graph with $n$ vertices, 3COL will always therminate after $a n^b+c$ instructions.
I claim that there is a polynomial algorithm to decide if a given triangle-free graph is 3-colorable (in particular it will decide if the graph is not 3-colorable):
This algorithm runs in polynomial time and decides the $NP$-complete problem if a triangle-free graph is 3-colorable, thus it can't exist unless $P=NP$.
I didn't see this kind of argument before, so let me know if you see some gap in my proof.