Fault-Tolerant Hello World
Befunge, Score 0

I think I cracked it - no single character deletion will change the output.
Deleting any character from line 1 changes nothing - it still goes down at the same place.
Lines 2 and 3 are redundant. Normally line 2 is executed, but if you delete a character from it, the &lt; is missed, and line 3 takes charge.
Deleting newlines doesn't break it either (it did break my previous version).
No test program, sorry.

EDIT: simplified a lot.

                              vv
@,,,,,,,,,,,,,"Hello, world!"&lt;&lt;
@,,,,,,,,,,,,,"Hello, world!"&lt;&lt;


A short explanation of the flow:


Befunge starts executing from top-left, moving right. Spaces do nothing.
v turns the execution flow downward, so it goes down one line.
&lt; turns the execution flow left, so it reads line 2 in reversed order.
"Hello, world!" pushes the string to the stack. It's pushed in reversed order, because we're executing right to left.
, pops a character and prints it. The last character pushed is printed first, which reverses the string once more.
@ terminates the program.