> Constructing the sentence is algorithmic.
No, it isn't. But it's a non-trivial point.
> Similarly, a program decides a set of problems(like does this Turing machine halt or does this diophantine equation have solutions) with access to its source code will be able to algorithmically generate the problem instance on which it will not halt. You can modify the program to create a new program which will use this information, but it will be a new program.
So this all depends on what you consider a "new program". Suppose we write a program that actually does this: analyzes its own code, algorithmically produces the Godel sentence for that code, then modifies its code to include that as an axiom, forever. That program is a program, and that program will also have a Godel sentence, but one which it cannot construct using that algorithm. You need a different algorithm to construct Godel sentences for programs that constructs Godel sentences on programs that don't construct Godel sentences.
The result is a hierarchy of Godel-sentence constructors. At any level in the hierarchy the procedure is algorithmic, but going from one level to the next is not. It's similar to the process of constructing the hierarchy of ordinals, which is also provably non-algorithmic.