You can run the navigation stack in conjunction with gmapping, see
http://www.ros.org/wiki/gmapping, to run without a static map. Instead of running the map_server and amcl, gmapping will provide the map and localization information to the navigation stack. As far as exploration goes, there is an exploration stack that uses frontier based exploration,
http://www.ros.org/wiki/exploration, that may serve your needs. However, its been a long time since I ran the exploration code, so I'm not sure how well it will really work. You could also, of course, write your own if you find that it doesn't suit your needs.