If I suspect my computer or cellphone is being monitored by an unknown attacker, what tools or techniques could I use to detect or identify such monitoring?
There's a broad spectrum of methods that could be used to monitor your communication.
External Monitoring ("Lawful Intercept")
Your attacker could be monitoring your communication upstream. This could be because they're working with your ISP, or they're sniffing your home network (wired or wireless). You said that your attacker knows things you typed... were you typing these over a clear channel?
Defense against upstream monitoring and local network sniffing: Don't send any communications in the clear. Use only encrypted channels, and use only protocols that provide you assurance that you know who is at the receiving end. The attacker will still see all of your communication, but (assuming the encryption is strong, you don't leak the key, and any passwords are strong) they will be unable to read it.
Defense against local network sniffing: Stop using wireless; disconnect the antenna from your access point, disable wireless in software. For your wired network, inspect your cables. If your cables go through the walls, run new cables between the router and computer that are exposed (visible). You may be able to detect sniffers through various techniques, but it isn't always possible.
Defense against anybody brute-forcing your encrypted communications: (Assuming you're encrypting everything...) Flood the attacker with noise. Through whatever communication channel you're using, make sure that you are always sending something -- random garbage. (It doesn't have to be random, anything will do -- the works of Shakespeare, the text of the tax code, etc.) It should still be encrypted; this makes it so that even if the attacker can feasibly brute-force your communications it is even harder because they won't know which comms are legit and which are noise.
Internal Monitoring (rootkit, keystroke logger)
If your attacker has hacked your computer or phone, there could be a monitoring process that is running and sending all of your keystrokes to the attacker.
Defense against rootkits/loggers: You can run a rootkit detector or anti-malware software to try to find it. If the attack is really clever or uses some new technique, you may not find the logger.
Defense to detect them: They have to get the keystrokes off the machine somehow. Run a sniffer. If you detect outbound traffic that is not yours, investigate it. It may lead you to the process that is sending your keystrokes. As another poster mentioned here, you can jailbreak your phone and run a sniffer to detect any unexplained outbound traffic. This is not foolproof; the logger could be using a covert channel that is not detectable using the common monitoring techniques. Careful analysis of a capture file might reveal a covert channel, but a sophisticated attacker might be using an out-of-band channel or other mechanism that is very hard to detect.
Defense to avoid them on your phone: Ditch the smart phone. Get a "dumb", disposable phone and a prepaid account. Use it for phone calls. Use your (wired) computer (see next item) for Internet commnication.
Defense to avoid them on your computer: Go to the store, buy a USB stick (best if you can find one with a physical read-only switch). From a reliable source, put a bootable copy of your OS of choice on the drive. Switch the drive to read-only. Boot from the drive. (This assumes that you are going to install a hardened copy of the OS onto your read-only drive.) For the most protection, don't access your existing HDD. Wipe it (with every reboot if you're paranoid) and use it as swap/tmp space.
Defense to distinguish between monitoring via rootkit and monitoring via network: Using a clean OS (see above), send a message that you want intercepted from your home network. If the message is intercepted, it is very likely that your network is compromised and not your computer.
If the attacker has placed listening devices or cameras in your home, workplace, or other areas that you commonly use, they could be monitoring you that way. Keep in mind that you could be watched through open windows, or someone could listen through the walls of a neighboring apartment.
Defense to detect this monitoring: (Assuming that you can get feedback on whether particular messages are captured.) Assuming you can surreptitiously disconnect your keyboard from your computer, type something that you want to deliberately be intercepted (in a situation where the keystrokes would not be echoed to the screen). If you find out that the communication was intercepted, you can assume that there's something monitoring your keyboard. Repeat as desired, possibly moving to different rooms. Repeat with the keyboard connected to the computer and characters echoed to the screen, but actual network comms disabled.
If your messages are only intercepted when echoed to the screen, you could be subject to Van Eck phreaking. In this case, you would need to shield your LCD from leaking electromagnetic emissions.
Defense: If you think your home and/or office is bugged, don't communicate from those locations.
Defense: If you think your phone is bugged, get another phone (see above). Never let the phone off your person.
Defense: Hire a specialist to sweep your home for RF bugs. (Or move.) After it is verified clean (or you have moved), apply physical security measures to avoid physical compromise and/or at least have the ability to confidently detect it.
Finally, don't discount the possibility that the person you are communicating with has been compromised. Maybe their computer/phone has been hacked, they are being monitored, or they are otherwise providing with your attacker with info. It's also possible that any servers/services that are relaying messages for you have been compromised and are disclosing your messages.
I'm going to assume, for the purposes of winning the bounty, that you aren't crazy, or paranoid, or schizo, or whatever.
Here's the thing about surveillance... If you KNOW its happening to you, but you can't figure out how it's being done, then you likely never will figure it out (or you're bonzo). At some point, you will have to resign yourself to the certainty that you are being monitored, and that there is nothing you will be able to do. Once you make that decision, the decision to stop fighting and investigating, there are several other options open to you.
First, you can just decide you just don't care. Let them listen to your personal business all they want, you just don't care anymore. This works especially well if you aren't doing anything to be ashamed of, or illegal, or against the prevailing party in the country. I don't know the political and legal situation in Brazil, so I can't really recommend this position either way.
If this isn't an option, you can also just disconnect and go dark. No information transfer means nothing to monitor. These guys can sit at their computers all day, and hear nothing but static from you. This means that they'll have to get more deep into your business to keep tabs, and run a greater risk of you discovering their methods, possibly bringing them to the attention of law enforcement or a civil rights group.
Lastly, you can change the game, and bombard them. If you can't continue 'in the clear', and you can't go dark, then you increase the 'noise' (it's called disinformation). You recite long strings of random numbers into your phone. Send cryptic texts to international numbers. Post buggy JPG's on international bulletin boards. Seed the output of dev/random on bittorrent. Encrypt stupid things, but use nothing larger than a 10 character key, with no symbols or numbers (that's about 40-60 days of cracking time). Call random people over skype, and use obscure phrases, odd mannerisms, an just plain gibberish. Wear a certain color shirt, and go to the same mailbox every Wednesday, while turning over rocks in the park. Leave random notes with GPS coordinates lying around. Surf google for strange phrases. You could turn any monitoring of you into a loss leading activity, which will force them to determine if you are REALLY a viable target. Maybe you are, in which case good luck. Otherwise, they will eventually fire whomever is monitoring you for wasting a metric ton of money.
Best of luck, solidarity, the jade falcon flies at midnight. Latitude: -58.21642, Longitude: 65.62804. xyzzyverboten.
I guess one way to see what's going on on your iphone would be to jailbreak it, run a 24/7 tcpdump (while not using the internet in order to keep the .cap small) output it to a .cap file and have a look at it in wireshark. Quite a bit of work to do, but with the right filters you can surely see if there's something going on.
That's obviously one definite technique to expose malware which is calling home via TCP/IP... GPS would be a different topic.
Same procedure can be done on Windows 7.
Okay - there are definitely two important points to remember here:
The technology is all simple stuff, but really, your government don't care - they have trouble justifying resource to track criminal gangs who are getting away with millions. Typing something into notepad and then hearing someone else talk about it is a little at odds with a government that you think is making a determined effort to snoop on you, don't you think?
So - ruling the government out of the equation, what other possibilities do we have?
(I wrote this bit before noticing you mentioned a neighbour who is a policeman - makes it even more likely:)
Someone who knows you - this is actually significantly more likely. A neighbour, colleague or friend would certainly be infinitely higher up my list of probables than a government. But again, what makes you so important that your communications are being tampered with?
Which brings me to the single most likely outcome, statistically:
The points you discuss in your question don't strike me as evidence of anything, I'm afraid. iPhones and other smart phones sometimes run slowly, apps are written by fallible humans, and to top it all off you say you haven't been able to detect anything.
You say you have security software up to date on your PC and have reformatted it, and you have a router with access controls (I'm assuming you do have them enabled?) so you are already doing the right things. Make sure your windows firewall is enabled, and perhaps look in to Microsoft Security Essentials.
So really, unless you are a valuable target, stop worrying and learn to love the internet :-)
Have you read about the Stuxnet virus? One place to begin reading about it is http://www.wired.com/threatlevel/2011/07/how-digital-detectives-deciphered-stuxnet/all/1
Then you can extrapolate the history to your question:
3 - If you remember the NSA Key inside windows (http://en.wikipedia.org/wiki/NSAKEY), you can see that rumours about what you're asking have being spreading long ago...
Go to, for example, the GCHQ website. Read what they say - they are the largest computing centre in Europe; they employ very many mathematicians and computer people; they are responsible for monitoring communications "from DC to light".
With that information you can invent various conspiracy theories about what they are capable of.
Mix in information from previous known work, for example the EU parliament report on ECHELON, and you can ramp up those conspiracy theories.
A lot of software is either insecure or installed and maintained so as to be insecure and most users are hopelessly insecure and clueless. Do governments need to install super secret backdoors into all software? Probably not. They just need to employ people who can 'hack'/'crack'.
No. (but I can not be trusted)
Many, my favorite is using half of a psychoactive chemical in a food product and half in a hygine beauty product. When a populatious uses enoguh of both types of products... Oh wait that's from Batman.
Every computer is monitored especially the ones monitoring the computers being monitored, but I can only guess who monitors those monitoring the monitors.
The stealthy capabilites of national governments are undeniable.
USA The bay of pigs
Israel Mossad agents caught on tape in Dubai
UK's George Blake
Austraila's ASIS with the Sheraton Hotel incident
France's DGSE with the Sinking of the Rainbow Warrior
Germany's MAD with surveilance of their own foreign minister Georg Leber