I imagined before each screen update, I could do the resizing.
You don't need to resize at each screen update. Depending on the monitor resolution you can resize all of your images, load different ones (bigger/smaller) or both.
I have always wanted to make a tutorial about this, but I really don't have the time right now.
You can use transformations which I don't know anything about, or you can resize your images individually depending on the screen resolution. Resizing it's the most easiest approach after the raw ALLEGRO_FULLSCREEN display option. But you won't notice the difference at least you add black bars in the left and right part of the screen to make the game keep its aspect ratio.
Now, the ideal way would be to not resize the images at all, and show more or less depending on the monitor resolution. A good example would be to play Angry Birds for PC, which resizes the view depending on your monitor resolution, or in case you want a resizing example the card game Spiders which comes with Windows.
The unique one in which you don't need to think about anything but just resize the windows is when using the ALLEGRO_FULLSCREEN flag. With the rest of them the first thing that comes to mind is collision detection, which obviously needs to change when the image increase or decrease. Now if you go with the "ideal" approach in which you don't change any image, the collision detection still the same, but the layout of the game will be your nightmare.
Neither of them are really difficult, the thing is if you're just used to set a flag... Obviously this will be something new that will take you some time.