Si, si debes hacer el session_start().
Mira:
index.php:
<?php
session_start();
...
?>
...
<head>
...
$(document).ready(function() {
$("#lol").click(function(){
$.post("tu_archivo_para_la_session.php", { name: "John", time: "2pm" },
function(data){
alert("Data Loaded: " + data);
//aqui procesas data, que no es mas que el "codigo fuente" de la web a la
que haces post una vez "montada".
//Por ejemplo:
if(data=='VERDADERO'){
...
}else{
...
}
});
});
});
...
</head>
...
<div id="lol">
</div>
...
tu_archivo_para_la_session.php
<?php
session_start();
$a = $_POST['...'];
$b = $_POST['...'];
...
...
...
if(...){
$_SESSION['...'] = ...
$_SESSION['...'] = ...
$_SESSION['...'] = ...
...
echo 'VERDADERO';
}else{
echo 'FALSO';
}
...
?>
Ves lo que sucede?
Index.php, tiene un divisor (por poner algo) que cuando lo clickas (por poner un evento), hace un $post() al fichero php determinado pasandole unos parametros a tu voluntad.
Este fichero php, tambien "inicia" session (ya que quieres la actual del servidor) y realiza lo que tu quieras. Al final, por ejemplo, mete en session lo que te interesa, y escribes (SOLAMENTE) "verdader". Sino, escribes "falso" y la session no la tocas.
Es un ejemplo. La idea es que todos los ECHOS que tu hagas en este fichero especial, son los que se leeran despues en DATA en tu index.php, ya que es como si hicieras "ver codigo fuente", para que me entiendas.
Verdad que si hicieras un php sin header, ni body ni nada de html con solo un "echo 'hola';", al hacer ver codigo fuente, verias solamente "hola"? Pues es básicamente esto.
Luego tu puedes escribir un "codigo fuente" que te venga bien, para luego parsearlo en javascript, o lo que ya es la ostia, es que puedes escribir XML o JSON, para luego especificarle a la funcion $post() que los datos llegan en este formato, para ya tratarlos directamente así en javascript, una joya vamos! 
Example: Gets the test.php page content, store it in a XMLHttpResponse object and applies the process()
JavaScript function.
$.post("test.php", { name: "John", time: "2pm" },
function(data){
process(data);
}, "xml");
Example: Gets the test.php page contents which has been returned in json format ()
$.post("test.php", { "func": "getNameAndTime" },
function(data){
alert(data.name); // John
console.log(data.time); // 2pm
}, "json");
Bueno, espero que veas mas o menos por donde van los tiros
En cuanto a esto:
Ya pero no puedo hacer un onclick="<?php $_SESSION['menu1']=true; ?>".
Seria "genial", pero tendriamos un problema gordisimo de seguridad, no crees? 
Lenguaje "servidor" se interpreta y traduce en tiempo de request.
Lenguaje cliente, se ejecuta en tiempo de response activo.
A pesar de todo, este tipo de "mezcla" es lo que te comentaba, que puedes usarlo para dar, por ejemplo, valores a variables particulares de javascript, para que cuando se escriba el script en el DOM, por así decirlo, ya tenga los valores correctos según PHP...
