I'll ignore "Does anyone else find this frustrating?" (see 5th bullet point in first set).
"What are possible solutions?" Add an index column (A is best for this) say containing
=row() copied down (and then convert to values or sorting could cause problems). Maybe format that column to make the index values more prominent than the headings for rows.
"Is it possible to have a cell index of 0 (eg A0)" As mentioned by @Al.E it is not possible. Any attempt at such a reference will give rise to an error.
However, given a mixture of zero- and 1-based indexing for the functions used in spreadsheets (provides training in awareness of the starting point!) it can be fairly easy to acclimatise to ignoring row numbers as a guide to number of items. Control totals and formulae to do the counting are almost as good as what you propose. There may also be the option to add say
Item1 anywhere in the sheet and copy down to automatically number each item, regardless of the start row.
Given that column labels are so often required and even when not are almost always advisable, it does sound as though 0:0 would be an excellent idea but my surmise is that this is a carry-over from the earliest spreadsheeting software (Wikipedia for example actually describes VisiCalc as "The first widely used normal spreadsheet with A1 notation") and that the power of the sheer numbercruching but lack of power of the processors on which it was performed meant that labels were hardly considered at that time. From what I can now recall, 1-2-3 had no requirement for labels (whereas some aspects of Excel for example will not work without them, and Google Sheets seems deliberately to copy Excel in many features).