Gareth never appears to me in Valeria, I guess the main quest lin eis broken without this?

When starting new game, once you are in the town, click on game options icon in lower left corner, and find "Reset Adventures" button in Game options tab. Click on it, and it will erase all the progress.

Also keep in mind, there are 2 kinds of saves in this game. One of them is autosave when you are in town, and the other one is save outside of towns. Each time you start "new game" you actually load the autosave from your last visit town. "Reset Adventures" button erases the quest progress from that autosave (however, it doesn't erase character progress and can be used as sort of "New Game+")..

See here.

AFAIK the main quest is not broken without his appearence. In my current playthrough he didn't appear at the beginning and i'am half trough the main quest without any issues.

He only appears once. So if you create a character, exit the inn, you get gareth's speech, enter inn, delete character, create new one, exit inn again - no more gareth.

Gareth only appears again if you "reset adventures" (under the game's options)

How do you actually delete a character though? I cannot figure it out and I have 5 joe-defaults that I don't want to touch just sitting there at the inn.

Place the unwanted PC in your party, open up their menu screen, and look to the far left. There should be various "Inn-Only" options, including delete.