If you're going landside, you could use the Kanku lounge - It's basically a "manga cafe" - http://www.kansai-airport.or.jp/lounge/

300 yen to enter (up to 30 minutes) + 100 yen for each additional 10 minutes
300 yen to use shower (a basic, plastic molded unit)
Soft drinks available for no extra charge.

So, if you move fairly quickly, I think you should be able to to freshen up, change clothes and grab a cup of java for 600 yen.