This is a case where looking at the workings of more retro hardware would be reasonable. Older hardware had strong limitations in both memory and processing power. Your 100+Mhz chip is far faster than most consumer-grade chips of the 80s and before. So while those CPUs needed dedicated graphics chips to be able to render, your much faster CPU can probably handle the task adequately.
I would suggest starting with something like the NES's tilemap-and-sprite architecture. These architectures are designed to be both memory efficient (getting a lot out of limited storage space) and computationally efficient in a line-by-line output, as they generated pixel data and sent it directly to the display device at the expected speed of a CRT.
The broad idea is this. A tilemap consists of two parts: a series of tiles and a 2D array of indices into the tile map that represents the image being created. The tiles are typically 8x8, and on the NES were 2-bits-per-pixel and the tiles used palettes. Or more specifically, the index into the tile map includes not just the index of a tile but also the index of the palette to use with that tile. So a tile is not inherently associated with a palette; the association is made at the point of use (technically, on the NES, the tile map and palette map were separate, as each 2x2 block of tiles all had to use the same palette).
To allow for scrolling, the tile map is bigger than the visible screen, and there is an offset that represents where the top-left corner of the visible screen is within the tilemap. Let this offset be at position Xoff and Yoff.
You can see how this makes row-by-row processing trivial. To generate a horizontal row for the horizontal position Ypos (in screen-space), you need to get the starting pixel within the tilemap. That requires transforming the XY position (0, Ypos) from screen-space to tilemap space. So you add to it the vector (Xoff, Yoff), hielding the vector ``Xoff, Yoff + Ypos)`.
Note that when doing any mapping from screen-space to tilemap space, that the tilemap space should wrap around in both the X and Y axes. So whenever you compute a new pixel in tilemap space, you have to wrap it around the size of the tilemap space.
Now, we need to break down this tilemap pixel into two 2D components: the tile index within the tilemap that gives us this this pixel, and the pixel within that tile that we need to fetch for this pixel. The tile index is just the tilemap-space pixel integer-divided by the tile size. The pixel coordinate is the tilemap-space pixel integer-modded by the tile size. Given an 8x8 tile size, you're doing this:
ivec2 tilemap_pixel = ...; //Compute the tilemap starting pixel as above.
ivec2 tilemap_tile = ivec2(tilemap_pixel.x & ~0x7, tilemap_pixel.y & ~0x7); //Mask off the lower 3 bits.
ivec2 pixel_in_tile = ivec2(tilemap_pixel.x & 0x7, tilemap_pixel.y & 0x7); //Mask off all but the lower 3 bits.
So given tilemap_tile, we now have the index of the tile we are currently working within. And pixel_in_tile gives us the pixel we're working in. So we can fetch that pixel, whose value can be mapped into a palette to produce the final color for that pixel. Or we can use it directly.
To get the next pixel is pretty trivial. We just increment pixel_in_tile.x by 1, modulo the tile size. If the increment exceeded the tile size, then we also increment tilemap_tile.x by 1, modulo the tilemap size. And you keep going until you've filled out the row of pixels.
There are many opportunities for performance optimization of such an algorithm.
The tiles probably represent the largest data. A 128 element tile set of 8x8 tiles, even at 2bpp, is 2K. But the thing is, those can be stored in ROM, since you're probably not changing the tiles themselves. The size of the tile map (assuming it must be in RAM) depends on the desired output resolution and the tile size. A tile map for 8x8 tiles that can cover a 320x240 screen is 1,200 bytes. Not exactly tiny. You'll need to take up more memory if you want room for smooth scrolling (and thus a larger tile map).
That being said, it's also important to note that the "output size" doesn't have to be the actual size of the display device. For example, if you intend to draw to a 1080p display device, you could still render to an internal resolution that's, for example, 8 times smaller, 240x135. It's easy to modify this algorithm to essentially generate the same pixel value 8 times in a row, as well as reusing the same line 8 times per 1080p line. Indeed, it wouldn't be too difficult to have this algorithm allow for subpixel scrolling (scrolling in 1080p space, not 135p space) and even adding some filtering between pixel values. A 240x135 "output size" tilemap would only require 510 bytes for the visible region, so you would have more room for a larger scrolling area.
