Paperboy draws a bunch of black sprites along the left side of the screen to cover up the glitches. Depending on the game this can be acceptable, but you only have a budget of 8 sprites per scanline and 64 total sprites, and this technique can eat up a lot of that budget.
Edit: as sibling comment noted, Paperboy does have custom logic on the cartridge, a 74HC161 4-bit counter. I think this is just used to switch between CHR banks.
There's an interesting parallel in Atari 2600 development here. When the screen is being drawn, the program must update the GPU registers in real-time with the progress of the electron beam across the screen. If the program doesn't update these registers quickly enough, graphic glitches will occur. Most games will poll the game state and prep for updating registers during each HBLANK period, but often this would take too long for certain scanlines and you'd end up with short black lines along the left margin. This was a very common issue, you can see it in lots of screenshots here: https://videogamecritic.com/2600tt.htm?e=85998#rev459
This wasn't a big problem, because TVs of the time often had big overscan areas (areas that were rendered, but covered by the TV's physical bezel). However, it was visible on many TVs, and today it is very visible under emulation. Activision's programmers found this unacceptable. Rather than perform the very difficult, or even impossible, task of making their code run faster than the HBLANK period, they instead chose to render the first cm or so of each scanline intentionally black! Notice the width of the screen in this screenshot compared to other nearby games: https://videogamecritic.com/2600ff.htm#rev203
More crazy tricks like this are described in the excellent "Racing the Beam" book by Nick Montfort and Ian Bogost.
Given that the 2600 has the same CPU core and predates the NES/Famicom by six years, it's not surprising that a lot of the same tricks apply :)
For the NES, depending on the registers in question, it can be easy or hard to update them during horizontal blank. Changing the scroll registers is easy, the PPU was designed to make that possible, and gave you a sprite zero hit test so you could get the timing correct--which is how Super Mario Bros. draws the HUD at the top of the screen.
With some extra hardware you can make this easier and get some cool effects like parallax. The NES exposes a NMI line to the 6502 on the cartridge connector, and you can wire up some logic on the cartridge to signal NMI for every scanline. Battletoads uses this effectively. Atari 2600 lacks NMI because the 6507 doesn't have a pin for it.
Certain registers are much more difficult to change during horizontal blank, but not impossible. For example, palette entries. This requires very precise timing so it was very rare to see it. Indiana Jones and the Last Crusade changes the palette entries mid-frame, but only for the title screen.
> gave you a sprite zero hit test so you could get the timing correct
This was a workaround to avoid Atari patents. On the 2600 you could write to a register to halt the CPU until horizontal blanking (commonly written as sta WSYNC), to get perfectly synchronized to the next scanline. Sprite zero is more flexible, but the timing isn't as precise.
Given that the NES had NMI and the 2600 didn't, I think that NMI probably should have been wired to horizontal blank to begin with. I'm sure that there is some reason why this wasn't done, but I can't understand why.
Lots of other games have custom logic in the cartridge. Super Mario 3 and Kirby's Adventure both have a scanline counter in the cartridge that works by snooping the graphics chip while it reads the sprite and background tiles. Because the access patterns were consistent and well understood, it could keep track of where the console was mid-frame and trigger an interrupt, making it much easier to do scroll splits and fancy raster effects. Go check out the final boss from Kirby's Adventure, or the crazy rotating stage in Butter Building, and remember that the NES is doing that with a single background.
Some of this may have been undefined behavior, but the MMC3 chipset involved was produced and manufactured by Nintendo. Whatever the original design was, Nintendo appears to have stuck with that same set of capabilities throughout the console's lifetime, and encouraged their developers to take advantage of all the tricks.
Edit: as sibling comment noted, Paperboy does have custom logic on the cartridge, a 74HC161 4-bit counter. I think this is just used to switch between CHR banks.