The following map suggests itself as candidate for an isomorphism
$\phi\colon K\to H\times C_2$:
$$ \phi(x)=\begin{cases}(x,0)&\text{if $x\in H$}\\(gx,1)&\text{if $x\in gH$}\end{cases}$$
Check it.
For part 4, note that $G$ contains some subgroups of the form $C_2^k$ (for example the trivial subgroup, where $k=0$). Among those subgroups, let $H\approx C_2^n$ be one of maximal size. If there exists $g\notin H$ we see that $K:=H\cup gH\approx H\times C_2\approx C_2^n\times C_s\approx C_2^{n+1}$ is a strictly larger such group (this is where we use finiteness!), contradicting maximality of $H$. Hence no $g\notin H$ exists, i.e. $G=H\approx C_2^n$. (This use of a maximal subgroup of the given type is in fact nothing else but a convoluted way of doing induction on the order of $G$, so your idea was the right one)
The number of non-isomorphic Abelian groups depends on the partition number of the exponents in the prime factorization. Let $P(k)$ be the number of ways to partition $k$ (for example, $P(4) = 5$, since we have $4, 3+1, 2+2, 2+1+1$, and $1+1+1+1$). Then for $n=p_1^{e_1} \ldots p_r^{e_r}$, there are
$$\prod_i P(e_i)$$
non-isomorphic Abelian groups of order $n$. You missed $2+2$ among the ways to partition $4$, corresponding to $\mathbb Z/(2^2\mathbb Z) \times \mathbb Z/(2^2\mathbb Z) = \mathbb Z/4\mathbb Z \times \mathbb Z/4\mathbb Z$.
You can use this formula to answer the original question. The first few partition numbers are:
P(1) = 1 1
P(2) = 2 2, 1+1
P(3) = 3 3, 2+1, 1+1+1
P(4) = 5 4, 3+1, 2+2, 2+1+1, 1+1+1+1
P(5) = 7 5, 4+1, 3+2, 3+1+1, 2+2+1, 2+1+1+1, 1+1+1+1+1
and they obviously increase from here. Now, if there are $4$ Abelian groups of order $n$, then we must have $e_1=e_2=2$, and we choose as bases the two smallest primes. Thus the number we are looking for is $2^23^2=36$.
Best Answer
The smallest $n$ is $6$:
1. $A$ is isomorphic to $\langle(1,2),(3,4),(5,6)\rangle$.
2. For $n=4,5$ the only subgroup of order $8$ which $S_n$ does contain is the dihedral group $D_4$ (and its conjugates, being a $2$-Sylow subgroup).