Why should the frequency of heads in a coin toss converge to anything at all? Suppose we have any kind of coin. Why should the relative frequency of getting a heads converge to any value at all?
One answer is that this is simply what we empirically observe this to be the case, and I think this is a valid answer.
However, my question is, is there some simple set of principles/axioms that apply to coin tossing from which we can derive this fact?

As long as your coin is memoryless (each flip independent),* such a limiting probability exists because randomly chosen variation tends to cancel itself out.  Mathematically, this fact is represented in the theorem that indepedent variances add: $$\mathrm{Var}(A+B)=\mathrm{Var}(A)+\mathrm{Var}(B)$$  Since the variation in $A$ (or $B$) is proportional to the square root (a concave function) of the variance, variances in a sum grow less quickly than the sum itself.
The average takes a sum of random variables and then divides by the number of random variables, which is proportional to the sum.  So the random variation in that average will be small.
We can formalize that argument as follows:
Remember that if a random variable $Y$ has mean $\mu$ and variance $\sigma^2$, then Chebyshev's inequality tells us $$\mathbb{P}[{|Y-\mu|>\delta}]\leq\frac{\sigma^2}{k^2}\tag{1}$$  Now, given $N$ coin flips $\{X_n\}_{n=1}^N$ (heads is $1$, tails $0$), the average number of heads is the random variable $$Y_N=\frac{1}{N}\sum_{n=1}^N{X_n}$$
Now, we only ever measure $Y$ up to some accuracy.  For example, have you ever really checked more than the 6th or 7th decimal place of a number?  So take $\delta=10^{-8}$ in (1).  The idea is to show that $\mathrm{Var}{(Y_N)}\to0$; then (1) will tell us that $$\mathbb{P}\left[{\left|Y_N-\frac{1}{2}\right|>10^{-8}}\right]\to0$$ and so any variation in the average will be indistinguishable to us.
So, OK, let's compute that variance.  Since each coin flip is independent, $$\mathrm{Var}{(Y_N)}=\frac{1}{N^2}\sum_{n=1}^N{\mathrm{Var}(X_n)}=\frac{1}{N^2}\cdot N\mathrm{Var}(X_1)=\frac{\mathrm{Var}(X_1)}{N}\to0$$ as $N\to\infty$.
(One can generalize this argument into a proof of Kolmogorov's Strong Law of Large Numbers.)

* The claim also holds exchangeable random variables, as in Ben's answer.  But the proof I know (page 185) uses a martingale convergence argument, which is complicated to explain if you haven't seen it.
