Is it possible that a signing algorithm produces no output?
I just can't imagine an algorithm that doesn't give an output wherein the algorithm above, it seems that it will always produce a certain output.


Actually, step 1 is randomized; that is, it will select a value of $r$ randomly (from some probability distribution).  If step 4 decides to rerun the procedure, then step 1 will likely generate some different value, and so the output would be different.


  It also seems to violate the definition of an algorithm by Knuth. 


Well, by Knuth's definition, it's a "computational method" rather than "an algorithm".  I don't think, in this case, the distinction is important, as the algorithm will terminate with probability 1 (and terminate quickly with high probability).  I don't believe that Knuth had randomized procedures (like this one) in mind when he wrote his definitions...