Okay,
I'll try and answer each part of your post in turn.............
No you don't need a dyno to make a useful Timing Map or any VE (fuel mixture) Table, etc.
It is possible to for example study factory tune files and compare the "GT" versions of the tune files with the more mundane models tune files to see what parameters had been changed.
Going by the assumption that a any car company would not validate and release poor tune files for production, complete with in some cases 100,000 mile (160,000km) warranties.
Some tune files can be down-loaded from the net, depending on software tuning companies. EFILive.com provide a free tune file reposiory here for example:-
www.holdencrazy.com
The tuning software I have experience of, has an additional software package ("moates road-runner") that allows anyone with it to make changes to a cars computer as you drive in real-time.
If you don't have this particular option, with the efilive scan & tune software for instance, you can log as you drive, notice a parameter that needs changing, stop the car; make adjustments to the tune-file and flash it in. It takes 2 minutes to re-flash a tune.
Then you can re-start and go with the changes made and if necessary continue logging to see what effect the change may have made.
The only thing to bear in mind here is that changes to things like Long Term Fuel Trims and other some other parameters such as throttle cracker and follower to name just two, can take up to 100-150kms for any alteration to become effective in the tune.
You are able to short-cut the time some of the parameters take by doing a PCM re-set which sets things like fuel trims back at zero (The PCM stores fuel trim information and has an adaptive learning capability for a whole load of things.
THIS MAY NOT BE THE CASE FOR ALL TYPES OF PCM,ECM.
Though I'd imagine most work in a very similar fashion now.
Getting back to the real-time logging capability that some of these full software packages have. It allow you to fit a wide-band O2 sensor and feed the AFR information into the data-logger. This gives instantaneous AFR readings that you can bring up on the lap-top or store it in the "black-box" (along with more than 100 different parameters, such as Spark Advance, Throttle Position, ECT, IAT, Cylinder Airflow, MAP, Oil pressure, IAC counts, Commanded AFR, etc, etc) as these black-boxes can be fitted with an SD card (from 1Mb up-ward) to store all this info.
Then when you are finished you can just plug it into a lap-top, down-load it and do a playback.
Although AFR is adjusted in these software packages I am familiar with. Nothing beats a dyno with a 4 or 5-gas analyzer for best results.
Especially a dyno where you can additionally hold speed and vary loads to get part throttle tuning sorted and the great bonus of being able to find where MBT (Mean Best Timing) is for best torque production at WOT for instance (Wide Open throttle) which will keep you well away from the dreaded detonation.
(It's amazing how many people still believe "More timing is better so most timing is best.")
This is only a fraction of the information available.
If you have a particular make of car I'd have a try at googling "tuning software for XXXXX" or something like that.
