"会社の株譲渡と連帯保証人の解除についての相談"

先日、配偶者も子も居ない叔父が亡くなり、兄弟である私の父とその弟である叔父の2人が相続人となりました。(両親は他界している)
叔父は小企業の代表取締役をしており、その会社の株の2分の1程度を保有、債務の連帯保証人となっているようです。
私の父達相続人はその会社を継ぐ意思はなく、会社の経理担当の方からは、新しい代表取締役(親族ではない)をたてるので、その人に全ての株を譲渡して欲しいと言われ、また、新しい代表取締役を連帯保証人にするため、亡くなった叔父を債務の連帯保証人からはずす事ができる(父や相続人の叔父は連帯保証人の責務は継がない)…と聞いています。
父達相続人としては、会社の事は全くわからないし、何より叔父の個人的な財産を相続したとしても会社の債務の連帯保証ができるような経済力はありません。なのでそれが可能なら、会社の方が言うようなカタチで…と考えていますが、実際のところ、そのような事(新しい代表取締役に新たに連立保証人になってもらい、父達相続人が連帯保証人の責務を負わずに済む事)は可能なのでしょうか?

新しい代表取締役を連帯保証人に”加える”ことと、
外すことができるかは別問題です。
会社側の判断や裁量によるものではなく、あくまでも当該債務の債権者の判断次第です。

会社財産が乏しい場合は、
債権としては相続財産を引き当てにしたいと考えるでしょう。

ご自身の対応(株式譲渡)はとりあえず保留として、
会社側の対応をひとまず待つべきでしょう。
場合によっては、相続放棄も視野に入りますので、財産処分は慎重にされるべきです。

会社側は今債権者(銀行)とのやりとりを進めていると話していましたが、(会社と銀行のやりとりが済んだ後)故人の連帯保証人としての責務が残るのかどうか確実に知りたい場合(会社の人からの口頭での連絡だけでは事実は分からないので)、銀行側に正式にその事実が証明されている書類か何かを請求したりなど、何か方法はありますでしょうか。

相続すれば連帯保証人となりますので、
利害関係人として、銀行に確認を取られてみてはいかがでしょうか?
相続に関しては熟慮中という留保(放棄の可能性有)は付けたうえで行動なさってください。