The paint does make a difference in whether or not you can easily paint over the background.
Watercolor, for example, does not easily cover other art and you would need to use a different technique for the background if you used this medium. Most other paints (like acrylics or oil) are thick enough that you can easily paint over the background without any effort.
With thicker paints you should paint the background of the image, get it as you like it, and then paint your subject over the top.
This has the down-side of not being very forgiving should you make mistakes to your main subject, fixing the background after touch-ups will be challenging.
With thinner mediums like Watercolor you would want to paint them independent of each other and not overlap them. I, personally, would paint the subject first and then follow with a watercolor background.
With watercolor you can use a common technique where you apply water to the paper before using any color. Carefully outline the dry subject with a wet brush and once the paper is wet, carefully apply your color.
The water will pull the color out of the brush and disperse it to the wet areas neatly without spillage. If you make a mistake with the wet brush, simply let it dry and try again before applying color.