Sure, you could generate a list of instructions and the addresses they appear at at run-time, which is basically how Graham's method works but you've got to make sure that you execute all possible code. The easy way to solve this is to lug around the original ROM with you and interpret anything you missed. A much, much more difficult alternative is to do something like FX!32 (the old X86->Alpha translator for Windows NT), which caches translated blocks on disk and updates this each time the program is run. But again, the problem here is that you have to retain the ROM.
In all cases, you will have to retain the ROM code for on-the-fly translation.