SQL Server - Defining and populating a new temp table column fails only once
When a stored procedure is executed for the first time, the query
  processor reads the text of the stored procedure from the
  sys.sql_modules catalog view and checks that the names of the objects
  used by the procedure are present.


Deferred Name Resolution and Compilation

That explains the observed behavior.  On the first call, the stored procedure body cannot be parsed and compiled because it references an object that doesn't exist: Column2.

When you create Column2 before invoking the procedure it will parse, compile and run.  Then in the third invocation the stored procedure has a cached plan, and doesn't need to be parsed again.  If you call dbcc freeproccache before Case_3 it will fail too.

And so the answer to:


  How can I add a new column to a temp table dynamically in a stored procedure and populate it with some values, without resorting to dynamic SQL? 


Is that you can't and shouldn't.  It's a very strange thing to even attempt.

You can normalize the the temp table and then use it in a subsequent stored procedure.  Like this:

CREATE or alter PROCEDURE TestAddTempTableColumn AS 
BEGIN
    IF NOT EXISTS
    (--don't require all callers to have their table declarations updated
        SELECT 1
        FROM tempdb.sys.columns
        WHERE
            object_id = OBJECT_ID('tempdb..#TestTempTable')
            AND name = 'Column2'
    ) ALTER TABLE #TestTempTable ADD Column2 VARCHAR(MAX) NULL

    exec TestAddTempTableColumn_impl
end

go
CREATE or alter PROCEDURE TestAddTempTableColumn_impl AS 
BEGIN
    INSERT INTO #TestTempTable(Column1, Column2)
    VALUES ('column1 value', 'column2 value')
END


But it strikes me as somewhat surprising to have code that creates a temp table, calls a stored procedure to load that temp table, and have the procedure alter your temp table.