Hombre, poder si se puede. PAra GBC hay un tutorial de dxman: http://wahackforo.com/t-C%C3%B3mo-editar-tileset-con-johtomap

Para GB, no sé si habrá una herramienta, pero si la hay, la desconozco. Aunque también puedes intentar cambiarlos con hex, aunque no te lo aconsejo si no tienes conocimientos previos, ya que es un trabajo bastante arduo y difícil.

Vamos, resuminedo, sólo he encontrado ese tutorial :XD:

Saludos!!