Coding an approximation to a Godel machine naively probably isn't that hard, relatively speaking - it would essentially be an extension to a symbolic computation system. What would be hard is running such a thing with any efficiency.
Schmidhuber has a great talk where he sets up the GM then drops the boom on practical implementations (I forget the details, but the exponent is ~3000, an impossible lifetime-of-the-Universe search space) and the audience laughs, but then he also points out that the self-improvement search may well find massive speed-ups, and so it is perhaps not as hopeless as all that.
