Eitan -
The move_base node is a single binary because it was built long before ROS had a good way to pass data efficiently between nodes. At the time, if you wanted to avoid a TCP connection and data copies, throwing things into a single node was the only way to go. In place of nodelets, move_base uses pluginlib (http://ros.org/wiki/pluginlib) and ROS wrappers (http://ros.org/wiki/navigation/ROS_Wrappers) to try to keep things reasonably modular.Re-factoring move_base to use nodelets would take a significant effort to do well, but there's no technical reason that it cannot be done. However, I don't think that it will actually make custom cost values any easier to implement. You can already modify the costmap ROS wrapper to subscribe to new topics. The real benefits of nodelets for the navigation stack would be improved introspection along with the ability to run components of move_base in separate processes when desired.
Overloading the PointCloud message for custom cost values doesn't make much sense to me. I think that it will only serve to confuse people and will likely make for some difficult code to read. It would be far better to modify the costmap to subscribe to a different message type for custom cost values. That message would probably just be an OccupancyGrid.
This option makes the most sense to me. I could see a service that allows users to set cost values on cells that are guaranteed not to be overwritten by any observation source. This service could consist of an OccupancyGrid that encodes the desired custom cost values.