We've discussed before the idea that NOT NULL constraints should be explicitly represented in pg_constraint, just like general CHECK constraints (this would allow them to be named, have sane inheritance behavior, etc). If we had that, then pg_attribute.attnotnull could indicate the OR of "there is a NOT NULL on this column" and "there is a pkey constraint on this column", and you'd just have to recompute it properly after dropping either kind of constraint.
Not happening for 8.4, but maybe someday someone will get around to it.
Warrants an entry in the TODO items list:
* make NOT NULL constraints have pg_constraint entries, just like CHECK constraints