It would be easy. In the information section of the Pokemon Summary would be a button called "Change Poké Ball". If you push it there would be a message that says: "Which Poké Ball you want Charmander (for example) to be in?" with a menu like the Poké Ball section of the bag with all the Poké Balls you have. When you choose one (for example a Great Ball) there would be another message that says: "Charmander is now in a Great Ball". And that's it.
I liked the idea, it would be a good case after changing the pokeball, the current one is discarded