I had same problem on Debian v 12 with Rails 3. Tried everything, and nothing worked finaly this worked, changed Gemfile to:

gem 'mysql2', git: 'https://github.com/makandra/mysql2', branch: '0.3.x-lts' # for Rails 3.x

got his from https://makandracards.com/makandra/515130-fix-mysql2-error-incorrect-mysql-client-library-version