PHP removes locale information from the operating system it is running on. As described in the documentation:
Note: The setlocale() return value depends on the system on which the
  PHP is running. It returns exactly what the function
  setlocale of the system returns.
So if the operating system displays the days of the week without the "-fair" the dates displayed by the locale will be like this.
Using your own example:
<?php
//teste.php
setlocale(LC_ALL, 'pt_BR', 'pt_BR.iso-8859-1', 'pt_BR.utf-8', 'portuguese');
echo strftime('%A', strtotime('now'));
echo PHP_EOL;
When I run this script:
adirkuhn: ~ $ php teste.php 
quinta
Okay, so compare it to my operating system.
First in the current locale (English):
adirkuhn: ~ $ date +%A
Thursday
And now with the pt_BR locale:
adirkuhn: ~ $ LC_TIME=pt_BR.UTF8 date +%A
quinta
So you have two options or add the "-fair" in hand with PHP even though it is easier.
Or changes the operating system locale file.
My test with the modified locale:
...
LC_TIME
abday   "<U0044><U006F><U006D>";"<U0053><U0065><U0067>";/
        "<U0054><U0065><U0072>";"<U0051><U0075><U0061>";/
        "<U0051><U0075><U0069>";"<U0053><U0065><U0078>";/
        "<U0053><U00E1><U0062>"
day     "<U0064><U006F><U006D><U0069><U006E><U0067><U006F>";/
        "<U0073><U0065><U0067><U0075><U006E><U0064><U0061><U002D><U0066><U0065><U0069><U0072><U0061>";/
        "<U0074><U0065><U0072><U00E7><U0061><U002D><U0066><U0065><U0069><U0072><U0061>";/
        "<U0071><U0075><U0061><U0072><U0074><U0061><U002D><U0066><U0065><U0069><U0072><U0061>";/
        "<U0071><U0075><U0069><U006E><U0074><U0061><U002D><U0066><U0065><U0069><U0072><U0061>";/
        "<U0073><U0065><U0078><U0074><U0061><U002D><U0066><U0065><U0069><U0072><U0061>";/
        "<U0073><U00E1><U0062><U0061><U0064><U006F>"
...
Date testing by the system:
adirkuhn: ~ $ LC_TIME=pt_BR date +%A                                                                                  
quinta-feira
And now the PHP test:
adirkuhn: ~ $ php teste.php                                                                                           
quinta-feira
							
							
						 
Before publishing as an answer see if this suits you: http://www.tiagomatos.com/blog/dia-da-semana-mes-e-ano-em-portugues-utilizando-php I know you don’t want to use array but the solution seems very simple
– Ricardo
I don’t want to do so. I’m using Laravel 4. And I have to return this through the Object
Carbon\Carbon, through the formatLocalized function. I cannot create "alterative methods".– Wallace Maxters
I understand I’m learning Cakephp and he’s also well xaropi
– Ricardo
I have a slight impression that this is configuration of
Ubuntu. My date returnsQuintaas in the operating system– Wallace Maxters
not how to concatenate or edit the value of this object with the value of the days of the week array?
– Ricardo
I may be wrong, but I believe no language returns the date with the suffix
feira.– Oeslei