I suggest the Game Boy to start with, it's a very nice system. People recommend NES too, I haven't worked with it a lot so I couldn't tell you much about it, though personally the lack of such simple instructions like an unconditional branch makes me shudder.
From my experiences, these things are only accessible through decompression, which requires the use of an assembly tool. But since I wouldn't be changing any of the games' physics by doing these things, will I still run into any of the aforementioned problems?
Most likely yes. In my experience I have to do a bit of code relocation in all but the most minuscule hacks (such as changing the hard-coded width of a sprite). Once you've done it a few times it will be easy as cake. My general technique is this:
1) Find some free space in the ROM. Say I found some at 1234 that is big enough to fit my code.
2) Change an instruction of the original routine to JMP 1234.
3) At the end of my routine at 1234 it will jump back.
More simply, you can use JSR/JSL to jump, and RTS/RTL to return. That way you can run the same code from multiple locations, since the return isn't tied to the original code location (though this may not
always be an option).
This depends on the instruction set. There are two different ways to implement JSR/RTS:
1) Push PC and Pop PC. JSR pushes the return address onto the stack, RTS pops an address from the stack and jumps to it. Most older CPUs such as Z80 and 6502/65816 use this.
2) PC -> Register and Register -> PC. Typically there's a register designated for this purpose called LR or RA. JSR copies the return address into RA, RTS jumps to the address in RA. Most newer CPUs such as R4300 and ARM use this.
If the CPU in question uses method 2, it may not be safe to arbitrarily insert JSRs into a routine, since you will overwrite what's in RA already. Routines that don't already have a JSR in them typically rely on this not being changed and don't back it up. You can back it up yourself before your new JSR, but it's often easier to just use an explicit jump to your new routine and jump back again.