Can I change Arduino program on-the-fly?
Replacing or modifying the existing code during run-time will require some form of uploading and over-writing the old code. This is deliberately not made straightforward or easy for these kinds of micro-controllers.

But you can change the program's strategy on the fly, if you anticipate the potential changes and include the code for each of the possibilities. 

For example, write a set of functions that each embody one of the various ways of operating, and, at run-time, select which function the program should use. You can change the selection by setting a value from the keyboard or the program could sense some external trigger such as a button-press, or a temperature reading and respond by changing the selection - the value of an int, perhaps. A switch statement can use that value to call the appropriate function at the appropriate time:

uint8_t strategy = 0;           // init to the default strategy

switch( selector ){
case(1):                // has event 1 happened?
   func1();
   break;

case(2):                // has event 2 happened?
   func2();
   break;

case(3):                // has event 3 happened?
   func3();
   break;

default:                // none of the above or undefined selector value
   funcDefault();
   break;
}


This does mean that all of the code for the possible operating strategies must be included at upload-time and share the program-memory space, but unless your job is very complex, even an Uno should be capable enough.

Update:


  I need to be able to update the device with some new functionality.


There is another approach which may or may not fit in an Uno but would be doable with a Mega 2560 or other larger-RAMmed machine: interpreted code.


Define a set of operations that includes whatever you'll need to operate your external device(s): the necessary I/O operations to read your sensors and control your hardware; to make logical and/or arithmetic tests and conditionally branch or call a function based on the test result; to listen for a user-signal from the terminal (for example) and return to the arduino program. This will be the "language" in which you write your control program.
Define a concise coding scheme to specify each operation and whatever data it needs, such as reading a temperature sensor and storing the result in a named place. If your control programs won't be too complex, you can get away with pre-defining A, B, ..., Z to be data registers of some appropriate type.
In C++, write an interpreter for this new language. It's program will consist of the codes you just defined. But this code will be seen as data by the interpreter. This is the key - this pseudo-code will live in RAM, where your interpreter - a collection of C++ functions - can read and execute it, and the Arduino program can download a new one, over-write the old one, and run the interpreter again.


Caveat: Like the Greek mythological Hydra, this is a job that can grow new challenges as you address the current ones, but it is doable if you keep it simple as possible and include only what you must have to make it work.

Run-time-interpreted code can take 10 - 50 times as long to execute as a natively coded application, so anything that can be pre-coded in C++ should be. The finer and more flexible your interpreted instructions, the more expressive you can be when writing the control program, but the interpreter will be more complex to write, slower to execute, and harder to debug. Design your language to be only as flexible as it must be to allow you to write new control algorithms.

If you try to invent an entire pseudo-computer, completely flexible and capable of being programmed for any and all purposes, you'll drive yourself crazy. Whole businesses have folded after sinking money and time into inventing a new and better computer and got so bogged down they couldn't recover. Don't go that route.

Start with the grossest, least flexible operations you can live with and get that much working. Discover its limitations and address those, and only those, one at a time, until you have a sufficiently flexible system in which to control your device.