My question – which I never heard answered and also can't find anything on the web for (searching just yields that there are apparently five countries without debt in foreign currency) – is whether there is any way for a country to create money without also increasing it's debt by the same amount.
Trivially yes. Some of the money in circulation is simply printed on paper or minted as a coin. That sort of money does not create any public debt. For example, in US treasury and in EU ECB can technically print as much dollar/euro bills as they want and then just 'gift' them to the government.
From accounting perspective ECB or treasury might treat currency in circulation as liability, but accounting is distinct from economics and you cannot simply transplant accounting definitions to economics. Economically, such liability is not recorded in measures of government debt.
the debt of the government is the wealth of the people and businesses of the nation
This is not true. This would only hold for closed economy of a country. If I (I am European) buy US treasury that treasury is indeed part of my wealth and since I live in the Netherlands part of the Dutch wealth, but no longer part of wealth of the US nation since I have neither US citizenship nor do I reside within US (depending whether you want to use residency or citizenship as deciding factor).
Nor does that imply excessive government debt is not a problem since empirically excessive levels of debt can hurt economic growth (e.g. see DiPeitro et al. 2012 or Mencinger et al 2015). This is just empirical observation regardless of what sort of theory you prefer to follow. However, its worth noting that this negative effects only kicks in at very high levels, and generally there is no magic number to say what level of debt-to-GDP is too high. Every country has bit different threshold.