To show that $1$ is not even:
I assume you can prove or accept that $a \cdot 0 = 0$ for all $a \in \mathbb{Z}$, the product of a positive and negative number is negative, and $2a > a$ when $a >0$.
If $1$ is even, then there must exists $a < 1$ such that $2a = 1$. However, the only $a < 1$, which is an integer, is $0$ and clearly $2 \cdot 0 = 0$. So $1$ can not be be written as $2 \cdot a$ for any $a \in \mathbb{Z}$. $1$ is odd.
Well, it certainly depends on how you define things and how abstract you want to be but I guess I would come up with what I think is the easiest answer for me.
We define a relation on $\mathbb{Z}$: $a \equiv b \mod n \iff n \mid a-b$
If $a \equiv b \mod n$ then $\exists q \in \mathbb{Z}: nq = a-b$, but by the division algorithm we can write $b=nk+r$ such that $0 \leq r < n$. If we replace this instead of $b$ we'll have $a - (nk+r) = nq \implies a -r = nQ' \implies a \equiv r \mod n$
Therefore every integer number is congruent to some number $0\leq r<n$.
If $n=2$, then $r$ is either $0$ or $1$ provided that you take the standard order on integers for granted. However, it's easy to prove that there is no positive integer between $1$ and $0$. Because if there was an integer, say $m$, such that $0<m<1$, then the set $S=\{x \in \mathbb{Z}: 0<x<1\}$ would be a non-empty subset of natural numbers and hence it has a least element by the well-ordering principle. Let $m_0 = \min(S)$. But field axioms on reals implies that $0<m_0^2<m_0<1$, that means $m_0 ^2 < m_0 \in S$ and that's contradiction. But we have already assumed a well-defined order on integers (in fact on $\mathbb{R}$ and all of its subsets) which could be challenged depending on how you want to define an order on integers and how you build them. Hence, I have so far shown that there is no integer number between 1 and 0, I guess with shifting by $n$ one can prove that there is no integer number between $n$ and $n+1$. But anyway, the relation I have defined on $\mathbb{Z}$ can be proved to be an equivalence relation. Therefore, it partitions $\mathbb{Z}$ into disjoint non-empty subsets that are our equivalence classes. We call the equivalence class of $0$ as 'even' numbers and call the equivalence class $1$ as 'odd' numbers. Your statements now are obvious because our partitioned sets are disjoint (therefore a number can't be both even and odd) and their union is all of $\mathbb{Z}$ (any number must be either even or odd). This could be proved independently by using only the definitions of partitions and equivalence relations.
Now it's easily possible to prove that our partitioned set inherits a natural algebraic structure from $\mathbb{Z}$. I.e. $[a] + [b] = [a+b]$ and $[a].[b] = [a.b]$ where $[a]$ represents the class of all elements equivalent to $a$.
I guess it should be easy to prove by induction that if $s(n)$ is in the same equivalence class as $n$ then we'll have only equivalence class, therefore, to avoid that, $s(n)$ must fall in the other equivalence class because we have only two equivalence classes in $mod 2$.
I hope my arguments aren't that terrible and naive. I'm not a logician after all.
Best Answer
Let $n$ be odd, i.e. an integer that is not even. Let $k$ be the largest even integer less than or equal to $n$. Since $k$ is even there is some integer $m$ with $k=2m$. Consider $n-k$, an integer (because it is the difference of two integers). It is nonnegative, because $k\le n$. It is not zero, since otherwise $k=n$ and then $n$ would be even. If $n-k\ge 2$, then $n\ge k+2$ and hence $k+2$ would be larger than $k$, less than or equal to $n$, and even. [Proof: $k+2=2m+2=2(m+1)$.] This contradicts the choice of $k$, so is impossible.
The only integer that is greater than zero and less than two is one. Hence $n-k=1$, so $n=k+1=2m+1$ for some integer $m$, as desired.