Would this be considered secure? Assume an algorithm that encrypts each letter in a string into a different one, using a key, but in such a way that if you were to change a single letter from the clean text, the encrypted text would look completely different. 

Also assuming each letter doesn't get encrypted to the same letter.

Here is an example (not generated by an actual algorithm)

Clean:


  Foo Bar Foo Bar


Encrypted:


  GjhetvbawmgYerujkgry


And another example


  Foe Bar Foo Bar


Encrypted, looks completely different from changing just one letter (and maybe even has a different length):


  HjengaieyHgnAuYehkawTGn


Would that be considered a strong algorithm?

My thoughts:

Statistical analysis can't happen (right?) because there is no symmetry in the encryption (for example, the two "o"s in "Foo" turn into different letters).

So how would a cryptanalyst find the key from such an algorithm?

(To clarify, I'm not asking if an algorithm is powerful, just how a cryptanalyst would look at it, assuming he knows the algorithm (and knows the key length) and has the ciphertext)
As a previous commenter pointed out, you're describing the avalanche effect.  In a block cipher, every output bit should be dependent on every input bit.  Changing a single bit of the key or a block of plaintext should, on average, cause half of the bits in the ciphertext block to change.  

A cipher that exhibits the avalanche effect is not necessarily secure.  It can still have statistical biases or be vulnerable to attacks such as differential or linear cryptanalysis.