No momento, não há driver proprietário da AMD para 16.04. Existe um driver beta, chamado AMD GPU-PRO, mas é um beta (sim, é redundante, estou cansado: P) e está limitado a poucos cartões.
Por enquanto, e provavelmente para sempre, a julgar pela forma como a AMD tratou suas cartas no passado, você está preso ao driver de código aberto, a menos que você faça uma de algumas coisas.
Por um lado, você pode comprar um novo cartão. Eu sei que você disse que não pode pagar, mas talvez seja hora de economizar para uma NVIDIA barata. Os cartões NVIDIA tendem a ser instáveis no Ubuntu, mas pelo menos recebem suporte por mais de dois anos.
Outra opção é fazer o downgrade. Faça o backup de /home/ para ter todos os seus dados de usuário e instale o Ubuntu 14.04. 15.10 é mais recente, mas está prestes a chegar ao fim de sua vida, já que não é uma versão LTS.
E, claro, você pode simplesmente orar e esperar por um driver AMD proprietário que funcione no 16.04. Quem sabe? Talvez algum desenvolvedor receba fglrx rodando no Xorg 1.18 (v1.18 é o que quebrou o fglrx de compatibilidade. O Xorg é o servidor de exibição.).
Honestamente, eu economizaria apenas para uma placa NVIDIA. Eu tenho uma caixa do Ubuntu configurada com gráficos da AMD em 16.04 e estou pensando em comprar uma placa VRAM NVIDIA de 1GB barata para substituir a AMD.