Probably yes, the NES is "easier" in this regard since char-rom is read from cart (so a cart only needs to provide the bits in correct order), the GB(C)'s have video-ram that contains all parts so you need to transfer it over. Don't exactly remember but iirc classic GB was a tad too slow for this, but GBC has a DMA that might be fast enough. (I've developed on classic GB mostly so don't know the characteristics of GBC mode).
I played a bit with original gameboy too. I was very surprised when, iirc, the cpu is not even fast enough to clear the screen in one vertical blank, or even in one frame! It takes like three to fully clear the map.
Yeah, you really need to structure your code around working with the tilemap system.
I did a small racing prototype with both vertical and horizontal scrolling and segmented my updates to 4x4 blocks of tiles per-frame (160x144 resolution so 20x18 of 32x32 tiles is visible at any point in time, so stippled updating 4x4 blocks outside of view is within the budget together with updating some of the tiles each frame)
This is false. You can do it in 1. It just involves mid-frame tile switching IIRC or using characters / sprites to fill in the rest.