That is one of the unfortunate things about working with hardware acceleration is you can only load so much uncompressed data into video memory at a time. Hardware acceleration was designed around 3D graphics, so 3D meshes would form the shape and motion while textures would create the look. With 2D graphics, you typically needs to use textures for all three of those aspects, and you need to do it at higher resolutions than a texture would typically need to be for a 3D object, resulting in massive amounts of video RAM usage.
The best thing you can do is streamline the process, reduce the number of frames of animation in your 2D objects, only load certain animations when absolutely necessary while unloading any that aren't being used, build objects out of multiple components whenever possible to avoid having to use a large series of images to animate them, and yeah, to really get your drawing speeds up, avoid switching the active source texture too often. (Allegro sub-bitmaps are OK to switch between so long as they all have the same source bitmap. Also look into the al_hold_bitmap_drawing() command.)
It should also be noted that transfering data from system RAM to video RAM is pretty darn fast, so in a pinch, as previously suggested, you can create a dynamic system for cycling certain character sets into and out of video memory as needed. That said, unless you're writing a 64-bit application (very unlikely if you aren't explicitly aware that you're doing it) you can still only address about 2 GB of system RAM reliably.
So long as you don't exceed 512 MB of video RAM usage, your game should be playable on most modern systems. Try to avoid exceeding 1024 MB of video RAM usage though because then only high-end systems will be able to play your game. You may also want to consider having texture quality settings so that players with less-capable hardware can load all the texture data in at half-size, which would cut memory usage down by 75%!