It would be pretty difficult going to Jeju without a car rental. You'll be limited in what you can see or do. I'd skip it if you can't get the driver's license. Sort of off topic, if you are set on seeing another place outside of Seoul and Busan, you should consider Gyeongju (assuming you're taking KTX between the two cities). It's along the way and is good for a couple of days' visit.