The easiest way would be to do what you just said there, but would be incredibly wasteful in terms of memory as you'd need 2 of each texture. If you've only got a handful of textures this is probably all you'll need.
If you need this on all your sprites (making it totally impractical to store 2 copies of each), here is something I've done before. It also gives you full control over the border, and you can do some interesting stuff with it.
1. In each textures alpha channel, draw the border in incorporate the border.
2. Use a cutout shader (or a blended cutout hybrid for iOS) to draw the sprites without a border.
3. Create a second shader, which takes a color and uses the alpha blended value. So basically, ignore the color channel of the texture, and use the alpha channel. Create this sprite and push it back in the main sprite, so you get a nice glow around it. You can tint this sprite and control the strength of the glow, and even cycle it if you'd like.
Hope that helps.