Most of the things you said do happen in Deus Ex, your actions may have consequences with civilians dying and so on, and permanent death is everywhere (be it on heavily scripted games de to story reasons, such as MW or not so scripted, like Fallout 3 and NV), once someones dead, theyre gone.
Honestly, closest thing there is to what youre asking is Deus Ex, seriously, thou, i must say, if what you want is a story and character driven fps\rpg then you will have to follow objectives and have scripted missions\events\whatever. Youve been speaking about Fire Emblem, but thats absolutely linear, sure, youll get a different line of text at the ending depending on whos dead, alive, friendships and so on but still, you follow a well laid out story all throughout and i see nothing wrong with that.
Then again, i would absolutely love a game like that, thou i disagree that we dont have any "true fps single player game yet"
Deus Ex HR The Darkness Bioshock 1 + 2 Metroid Prime 1 to 3
I WOULD say Half Life, except that it bores me to death for some reason, thou must people love it.
Wait for the PSN release of Serious Sam 3 BFE. I have it on Steam and it's awesome. Take classic Serious Sam and use the right aspects of "realistic" modern shooters like highly detailed graphics, aim down the sights, more realistic shooting (the first 2 Sam games didn't have guns reload, you just fire 100's of bullets,) try to tell more of a story this time, and keep classic elements like health items instead of regenerating health, being able to carry every gun in the game, and having lots of very challenging enemy encounters. It's the most ambitious Serious Sam game to date and it shows. If you want a great single player FPS that never has a dull moment and uses only the best aspects of modern shooters then it's very worth 40 bucks.