Shred an internal or system partition
Eventually I solved it by connecting the device to my pc, running adb shell and then running su in order to grant root privileges.

After that, to list all the partitions, I used the df command - and in each partition I generated a file big enough to fill all of the free space with random data (generated using the command dd if=/dev/urandom of=junkfile.txt bs=1048576 count=AmountOfMBs, as explained here).

Note that this method still doesn't shred the space that's currently in use on the device, so before going through this whole process I did a factory reset and then signed-in with a dummy account.