Have a look at Vespucci. If your phone has enough memory (>400MB), it might be exactly what you are looking for. It works on my SIII clone, although the tablet is a bit more practical…
I think it is usually best to use the phone for recording tracks and making notes etc, then downloading this data to a PC, before actually editing the map. As it is much easier to map things accurately if you have a large screen and a mouse. Plus you can use a variety of different sources on the PC, eg Bing aerial imagery along with the GPS tracks.
For on the phone, there’s a variety of apps to record a GPS track. eg OSMTracker, or OsmAnd, or My Tracks.
OSMTracker will also let you add marker for interesting points, eg postboxes, footpaths etc.
For house numbers and house names, Keypad-Mapper 3 is very good, it lets you map lots of numbers quickly. And yes, it is definitely worth mapping house names as well as numbers.
Also, you could try taking photos of things of interest, and geotagging the photos. This is often quicker than typing in house names etc on a small keyboard.
I would also recommend Osmand … it has features to record GPX tracks, read and open new Openstreetbugs, Upload POIs (only single nodes) directly to the main OSM Server, add markers to the map that you can name freely (I mean the “set favourite” feature) and edit the map later on PC.