After two days of research and browsing the web I have finally found a solution and been able to save my own Raspberry Pi system (not having to reformat the SD card and start from scratch)!
NOTE: This answer is pretty long. If you want to get to the actual solution quickly, I've added a header that you can scroll down to. I do recommend you read the whole answer though, as it may bring some insight into the differences between the Raspbian distribution and other Linux distributions as well as clarity to why a lot of the suggested solutions you find across the internet may not work on your Pi.
So normally, in a Linux environment, the quickest way to repair the broken sudo without even having to reboot is by using PolicyKit or the pkexec -command like this:
pkexec visudo
But on the Pi it most likely won't work, it will ask for the root password, but no password is accepted. (I mean, do you even remember setting a root password? Wait, you do? Then skip to the asterisk*.)
Some Linux distributions, for example Ubuntu, come with a recovery mode that can be accessed by holding down the shift-key during bootup and offers a user-friendly interface and allows one to be dropped into a root shell prompt where one could get access to fix the broken files. The Pi's Raspbian Linux distribution does not come with that kind of a recovery mode so that solution is not a solution for us. Yet the Pi does prompt you at bootup to hold down the shift-key to enter some kind of recovery mode and by entering the Pi's recovery mode or the NOOBS dialog we are surely on the right path towards repairing the broken sudo on our Pi.
Another common way of repairing sudo is by booting into single-user mode which gets you to a root shell prompt. The way you do this is by adding the word single to the end of the cmdline.txt -file on the system's boot partition. The next time your system boots up it will boot into single-user mode.
We can easily try this solution on our Pi because, conviniently, the Pi's recovery mode or the NOOBS dialog allows us to edit the cmdline.txt -file. In the recovery mode or the NOOBS dialog, by pressing the "Edit config" -icon you open up an editor that lets you edit two files, one of which is cmdline.txt. By pressing "OK" in the editor your changes are saved.
Unfortunately, when you boot into single-user mode or "rescue mode" on the Pi, you'll most likely get the following message:
Cannot open access to console, the root account is locked.
See sulogin(8) man page for more details.
Press Enter to continue.
This – as well as why the previously mentioned root password prompt didn't accept any passwords – is because Raspbian, by default, has no password set for the root account. This is not to be confused with a password that is nothing or that no password would be required. Raspbian, just like a handful of other Linux distributions (for example Debian which Raspbian is a derivate of), expects the user to operate as root through sudo and not through the account itself. Hence the root account is in the "lockdown" state that we are experiencing.
*If you set the root password yourself, for example through the command sudo passwd root, then you should be able to use the pkexec -command and boot into single-user mode. Note that when you do this, you need to use sudo, so this is obviously not a solution once sudo is broken, but I point this out because this is probably why some people found success in fixing their Pi's when applying the solutions suggesting the pkexec -command or single-user mode. These people had at some point gone and manually set a root password, unlocking their system's root account.
The Solution
This blog post explains how to do what we need to do. The steps are almost identical to the steps we took when trying to repair sudo through single-user mode. You don’t have to do all the cumbersome stuff the blog post mentions in order to edit the cmdline.txt -file, instead just do it in the NOOBS dialog. The key is to add init=/bin/sh to the end of the cmdline.txt -file. With that snippet added, the next time you boot up your Pi, you will be dropped into a root shell prompt.
Initially, the file system will be loaded in read-only mode, so before being able to edit anything, you’ll have to remount the root partition in read and write mode by executing the following command:
mount -o remount,rw /dev/mmcblk0p2 /
Now you should be in a root shell prompt, where you can freely edit any file, including the broken sudo files.
