Do all proteins start with methionine?
You are correct in thinking that since the translation of mRNA begins with AUG, which codes for methionine, then all proteins should contain a methionine at their N-terminus (aka start site). But, it is indeed not so. First of all, I want to mention about variations in start codon. As you say, AUG is not the only, but actually the most common, start codon, and it codes for methionine in eukaryotes, or formylmethionine in prokaryotes but only at the start site. But, this start codon can also vary and become GUG or even UUG, coding for valine and leucine respectively. And the twist is, it still codes for methionine or formylmethionine1. In rare cases, such as heat shock, other codons like CUG, ACG, AUA and AUU, are also used for initiation 2. It is so because start codon itself is not sufficient to begin translation, other nearby factors, like the Shine-Dalgarno sequence, or initiation factors, also play a role. One such factor is the initiation tRNA. At the beginning of translation, tRNAMet or tRNAfMet binds to the small subunit of ribosome. So, whatever be the start codon, the first amino acid will be methionine3.

Now, coming back to the main question, N-terminal methionine, although being the first amino acid, is not present at N-terminus of all proteins. This is because of a process that is known as post-translational modification. After a polypeptide is completely translated from mRNA, it is modified at different places by different enzymes, which are regulated by different (internal or external) factors. There are more than a hundred post-translational modifications known4, one of which is the removal of methionine from the N-terminus of a polypeptide. N-terminal methionine is removed from a polypeptide by the enzyme methionine aminopeptidase5.

The question which immediately comes to mind is Why are proteins modified after translation? Well, there can be various different causes of it. First of all, post-translational modifications are regulated by many factors, and this process is called post-translational regulation6. Another point is cell targeting. Attaching different groups to polypeptides makes them more stable at their target location. For example, by attaching lipid molecules to polypeptides (in a process called lipidation) makes the polypeptide more stable and suitable for cell membranes4. A yet another factor is increasing stability. Yes, you read it right, in some cases, N-terminal methionine can destabilize a protein! For example, an extra N-terminal methionine not only destabilizes but also disrupts the native folding configuration of $\alpha$-lactalbumin7. There can be numerous other factors too, which promote removal of N-terminal methionine from polypeptides.

Thus, in short, No, not all proteins contain a methionine at their N-terminus. I hope this helps!

References:

 1. Touriol, C., Bornes, S., Bonnal, S., Audigier, S., Prats, H., Prats, A.-C. and Vagner, S. (2003), Generation of protein isoform diversity by alternative initiation of translation at non-AUG codons. Biology of the Cell, 95: 169–178. doi:10.1016/S0248-4900(03)00033-9

 2. Ivanov IP, Firth AE, Michel AM, Atkins JF, Baranov PV. Identification of evolutionarily conserved non-AUG-initiated N-terminal extensions in human coding sequences. Nucleic Acids Research. 2011;39(10):4220-4234. doi:10.1093/nar/gkr007.

 3. Sherman, F., Stewart, J. W. and Tsunasawa, S. (1985), Methionine or not methionine at the beginning of a protein. Bioessays, 3: 27–31. doi:10.1002/bies.950030108

 4. Post-translational modification - Wikipedia

 5. Liao, Y.-D., Jeng, J.-C., Wang, C.-F., Wang, S.-C. and Chang, S.-T. (2004), Removal of N-terminal methionine from recombinant proteins by engineered E. coli methionine aminopeptidase. Protein Science, 13: 1802–1810. doi:10.1110/ps.04679104

 6. Wolfgang Schumann; Wolfgang Schumann (Prof. Dr. rer. nat.) (2006). Dynamics of the bacterial chromosome: structure and function. Wiley-VCH

 7. Chaudhuri, T. K., Horii, K., Yoda, T., Arai, M., Nagata, S., Terada, T. P., &amp; Kumagai, I. (1999). Effect of the extra N-terminal methionine residue on the stability and folding of recombinant alpha-lactalbumin expressed in Escherichia coli. Journal of Molecular Biology, 285(3), 1179–1194. doi:10.1006/jmbi.1998.2362